[백준 2133번] 타일 채우기 - 파이썬(python)

2133번: 타일 채우기

분류

• 다이나믹 프로그래밍

문제

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

입력

첫째 줄에 N(1 ≤ N ≤ 30)이 주어진다.

출력

첫째 줄에 경우의 수를 출력한다.

풀이

• 타일을 채울 수 있는 방법의 수를 구하는 문제이다.
• n이 홀수라면 타일을 모두 채울 수 없으므로 0을 출력하고 짝수라면 타일을 채우기 시작한다.
• n=2일 경우 3X2로 3가지의 경우가 존재하므로 저장한다.
• n=4일 경우 3X4로 2인 경우가 2번 있으므로 3X3하고 4인 경우 2가지를 더한다.
• 이렇게 계속 더해가면서 점화식을 구성한다. 이전 값X3에 더한값*2 +2한다.

코드

n = int(input())

dp= [0]*(n+1)

# n이 홀수일 경우 타일을 모두 채울 수 없으므로 0출력
if n % 2 == 1:
    print(0)

else:
    dp[2]=3
    # 4부터 for문으로 dp배열 채우기
    for i in range(4, n+1, 2):
        # dp를 채우는 점화식
        dp[i] = 2 + dp[i - 2] * 3 + sum(dp[:i - 2]) * 2
        #n=2나 n=4를 하나의 묶음으로보고 계산한다.
    print(dp[n])