[BaekJoon] 11727 2xn 타일링 2 (Silver 3) - Python

문제

 

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

아래 그림은 2×17 직사각형을 채운 한가지 예이다.

---

입출력 예시

 

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

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

 

입력예시1)

2

출력예시1)

3

 

입력예시2)

8

출력예시2)

171

 

입력예시3)

12

출력예시3)

2731

---

코드

n = int(input()) # n 입력
dp = [0 for _ in range(1001)] # dp리스트 선언

dp[1] = 1 # n = 1일 때 1가지
dp[2] = 3 # n = 2일 때 3가지
for i in range(3, 1001):
    dp[i] = (dp[i - 2] * 2) + dp[i - 1] # 점화식 적용
    # n = 1: 1가지
    # n = 2: 3가지
    # n = 3: 5가지
    # n = 4: 11가지
    # n = 5: 21가지
    # .
    # .
    # .
    # n: (n - 2)번째 * 2 + (n - 1)번째

print(dp[n] % 10007) # 10007로 나눈 나머지 출력

---

실행 화면

---

채점 결과