[코딩 테스트 연습(파이썬/Python)] 백준 11727번 _ 2 X n 타일링 2

https://www.acmicpc.net/problem/11727

11727번: 2×n 타일링 2

[문제]

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

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

[입력]

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

[출력]

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

 

[아이디어]

1) n=1일 때는 1을, n=2일 때는 3을 출력해야한다.

2) n=3부터는 앞 1칸을 세로로 채웠을 때(ⓐ)와 그렇지 않을 때(ⓑ)로 구분한다.

ⓐ인 경우는 1가지, ⓑ인 경우는 2가지가 있다.(가로 2개로 앞 2칸을 채운 경우 + 2*2 타일을 사용한 경우)

3) 즉, 2)에 의하여 n번째 항의 구하는 값은 (n-2번째 항의 값)x2 + (n-1번째 항의 값)과 같다.

 

n=int(input())
dp = [1,3]
for _ in range(n-2):
    dp = [dp[1],2*dp[0]+ dp[1]]
print(1 if n==1 else dp[-1]%10007)