[BOJ | Python] 11727번: 2xn 타일링 2

https://haerxeong.tistory.com/25

[BOJ] 11726번: 2xn 타일링

위 블로그를 참고하면 이해가 될 수도!

---

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

 

문제

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

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

 

입력

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

 

 

출력

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

 

풀이

n = int(input())
dp = [0] * (n + 1)

for i in range(1, n + 1):
    if i == 1: dp[i] = 1
    elif i == 2: dp[i] = 3
    else: dp[i] = dp[i - 1] + dp[i - 2] * 2
    dp[i] %= 10007

print(dp[n])

위 블로그 링크와 비슷하다. 1과 2를 조합하여 수를 구성하되, 2의 버전이 두 개인 것이다.

 

1 = 1

2 = 1+1, 2, 2'

3 = 1+1+1, 2+1, 2'+1, 1+2, 1+2'

 

위 예시를 보면, 2를 만드는 경우의 수에 + 1를 더한 것 (== 2를 만드는 경우의 수와 동일) + 1을 만드는 경우의 수에 두가지 버전의 2를 더한 것 (== 1을 만드는 경우의 수 * 2)

 

따라서 dp[i] = dp[i - 1] + dp[i - 2] * 2 라고 작성할 수 있다.