[BAEKJOON]백준 11726번 2xn 타일링 문제 파이썬(Python) 풀이 - 다이나믹프로그래밍(Dynamic Programming, DP)

문제

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

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

입력

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

출력

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

예제

입력1

2

출력1

2

입력2

9

출력2

55

코드

from sys import stdin
from collections import defaultdict


class Solution:
    def tiling(self, n: int):
        if n == 1:
            return 1
        if n == 2:
            return 2
        dp = defaultdict(int)
        dp[1], dp[2] = 1, 2
        for i in range(3, n+1):
            dp[i] = dp[i-1] + dp[i-2]
        return dp[n] % 10007


print(Solution().tiling(int(stdin.readline())))