[백준] 2133 타일 채우기 (Python 파이썬)

https://www.acmicpc.net/problem/2133

2133번: 타일 채우기

문제 설명

3×N 크기의 벽을 2×1, 1×2 크기의 타일로 채우는 경우의 수를 구해보자.

---

풀이 과정

먼저, 벽을 체울 수 있는 경우의 수를 구해보자.

 

벽의 가로길이가 홀수라면 벽을 가득 체울 수 없다.

예를 들어, N = 1 이라면 아래 한 칸이 남기 때문에 벽을 체울 수 없다. (타일은 2x1과 1x2만 존재하기 때문에)

[그림1]

N = 2 일때는 다음과 같이 3가지 경우의 수가 존재한다.

[그림2]

 

N = 4 일 때는 가로를 반으로 나눠 N = 2가 2개 있다고 생각할 수 있다.

그래서 앞의 3가지 x 뒤의 3가지 = 9 가지 경우의 수가 나타날 수 있다.

여기에 다음과 같은 모양의 벽 2가지를 더 추가해야 한다.

그래서 총 11가지 경우의 수가 존재한다.

[그림3]

이 때, 위의 벽의 모양처럼 더 추가해야 하는 벽은 

N이 2가 커질수록 2가지씩 더 늘어난다.

(직접 그림을 그려보면 더 이해하기 쉬울 것이다.)

 

이를 활용하여 N을 끝 지점으로 가져가보자.

끝점으로부터 2칸을 채워야 하는 경우는 다음과 같이 3가지 경우가 존재한다.

 

[그림4]

이 경우의 수는 3 x DP[N-2]가 될 것이다.

여기에, 위의 [그림3]에서 그린 것 처럼, 가로가 N일 때만 가능한 경우의 수가 2가지 존재하기 때문에 2를 추가한다.

그럼, DP[N] = DP[N-2] * 3 + 2 라는 점화식을 세울 수 있다.

 

하지만, 여기서 한 가지 더 고려해야 할 점이 있다.

끝점으로부터 4칸 이상이 남았을 경우에는 현재 상태에 [그림3]처럼 그 타일만의 고유 모양 2가지를 추가할 수 있기 때문에 2부터 N-2 이전까지의 각 칸에 +2를 해주어야 한다.

 

따라서, 이들을 총 고려한 점화식은 다음과 같다.

DP[N] = DP[N-2]* 3 + 2부터 N까지의 DP값에 x2 

 

이를 파이썬으로 나타낸 코드는 다음과 같다.

n = int(input())

dp = [0]*(n+1)

if n % 2 != 0:
    print(0)
else:
    dp[2] = 3
    for i in range(4, n+1, 2):
        dp[i] = dp[i-2] * 3 + 2
        for j in range(2, i-2, 2):
            dp[i] += dp[j] * 2

    print(dp[n])

 

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !