[백준 python 11727] 2 x n 타일링 2

[Silver III] 2×n 타일링 2 - 11727

문제 링크

성능 요약

메모리: 31120 KB, 시간: 44 ms

분류

다이나믹 프로그래밍

제출 일자

2024년 10월 17일 11:41:58

문제 설명

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

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

입력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)

출력

첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

풀이

n = int(input())
dp = [0, 1, 3, 5]

for i in range(4, 1001):
    dp.append(dp[i-1] + dp[i-2] * 2)
    
print(dp[n] % 10007)

 

n이 1일 때부터 그림을 그려 확인해봤다.

n이 1일 때, 경우의 수는 1이고,

n이 2일 때, 경우의 수는 3이고,

n이 3일 때, 경우의 수는 5이고,

n이 4일 때, 경우의 수는 11이 나온다.

이를 확인해보면 점화식은 `dp[i - 1] + dp[i - 2] * 2`가 나오게 된다.