문제 설명

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

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

입력

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

출력

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

풀이 코드

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
import sys


def main():
    n = int(sys.stdin.readline())

    counts = {1: 1, 2: 2}

    for i in range(3, n + 1):
        counts[i] = (counts[i - 1] + counts[i - 2]) % 10007

    print(counts[n])


if __name__ == "__main__":
    main()

CHECK!

딱히 어려운 점 없었음.
직사각형 하나를 가로로 두개 놓는 경우와, 세로로 하나 놓는 경우, 각각 2x(n-1), 2x(n-2) 크기의 직사각형을 채우는 방법의 수와 같게 됨
이를 dictionary 형태의 변수에 저장하는 형태로 구현함으로써 시간 복잡도를 줄임