[백준/BOJ] 1793 - 타일링

1793 - 타일링

문제

2×n 직사각형을 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×17 직사각형을 채운 한가지 예이다.

코드

while True:
    try:
        N = int(input())

        dp = [1, 1, 3]

        for i in range(3, N+1):
            dp.append(dp[i-1] + 2 * dp[i-2])
        print(dp[N])
    except:
        break

한마디

다이나믹 프로그래밍의 가장 기본적인 유형인 타일링 문제이다.
i-1 까지 타일이 채워져 있다면 그 다음에 올 타일은 2 X 1짜리 긴 타일 하나뿐이다. 반면 i-2 까지 타일이 채워져 있다면 2 X 2짜리 타일 한 개 혹은 1 X 2짜리 타일 두 개가 올 수 있기 때문에 위와 같이 점화식을 구성했다.

1793번: 타일링