티스토리 뷰

728x90
반응형

문제

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

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

tile

입력

첫째 줄에 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())))
728x90
반응형
댓글
반응형
250x250
글 보관함
최근에 달린 댓글
«   2024/03   »
1 2
3 4 5 6 7 8 9
10 11 12 13 14 15 16
17 18 19 20 21 22 23
24 25 26 27 28 29 30
31
Total
Today
Yesterday
링크