[python] 2×n 타일링

백준 11726번

문제 설명

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

아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

풀이

2xn 직사각형의 가장 오른쪽을 채우는 조건을 생각해보자

가장 오른쪽을 채우는 경우의 수는 위 그림처럼 (발그림 ㅈㅅ)

1. 2x1 타일이 한 칸을 차지
2. 1x2 타일이 두 칸을 차지

이렇게 두 가지 경우의 수밖에 없다.
첫 번째 경우 칸을 1 차지하니까 나머지 부분은 자연스레 n-1이 될 것이고
두 번째 경우 칸을 2 차지하니까 나머지 부분은 n-2가 될 것이다.

고로 나오는 점화식은 다음과 같다.

dp[n] = dp[n-1] + dp[n-2]

제출 코드

import sys

n = int(sys.stdin.readline())

dp = [1] * (n + 1)
result = 0

if n == 1:
    result = 1
else:
    for i in range(2, n + 1):
        dp[i] = dp[i - 1] + dp[i - 2]

    result = dp[n] % 10007

print(result)