백준: 2133 타일 채우기

문제

2133번: 타일 채우기

 

문제 풀이

 3xN 크기의 벽을 2x1, 1x2 크기의 타일로 채우는 경우를 구하는 문제이다. 문제를 풀기 위해 경우를 찾아보면 다음과 같은 규칙을 찾을 수 있다.

 

• N이 홀수인 경우 경우의 수는 0이다.
  • 2x1, 1x2로는 N이 홀수인 경우 채울 수 없다.
• N = 2
  • 3가지 경우의 수
• N = 4
  • 2의 경우의 수 * 3 + 2
• N = 6
  • 4의 경우의 수 * 3 + 2의 경우의 수 * 2 + 2
• N = 8
  • 6의 경우의 수 * 3 + 4의 경우의 수 * 2 + 2의 경우의 수 * 2 + 2
• `dp[N] = dp[N - 2] * 3 + dp[N - 4] * 2 + ... dp[N-N] * 2`

 

코드

from sys import stdin


if __name__ == '__main__':
    n = int(stdin.readline())
    dp = [0] * 31
    dp[0], dp[2] = 1, 3

    for i in range(4, n + 1):
        dp[i] = dp[i - 2] * 3

        for j in range(4, i + 1, 2):
            dp[i] += dp[i - j] * 2

    print(dp[n])