[백준/BOJ] 11726 - 2 X n 타일링

11726 - 2 X n 타일링

문제

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

코드

N = int(input())

dp = [0] * (N+1)

if N == 1:
    print(1)
elif N == 2:
    print(2)
else:
    dp[1], dp[2] = 1, 2

    for i in range(3, N+1):
        dp[i] = dp[i-1] + dp[i-2]

    print(dp[N] % 10007)

한마디

손으로 조금만 그려보면 점화식을 쉽게 찾을 수 있다.

11726번: 2×n 타일링