[백준/11727/파이썬] 2*n 타일링 2

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

11727번: 2×n 타일링 2

Problem

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

조건

• 첫째 줄에 n이 주어진다. (1 ≤ n ≤ 1,000)
• 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 10,007로 나눈 나머지를 출력한다.

SOL

이용할 수 있는 사격항 타일은 (1*2,2*1,2*2) 3가지 종류가 있다.

마지막에 올 수 있는 타일을 생각해주면, 이 3가지 경우의 수 밖에 없다.

모든 타일들의 경우의 수는 1*2 타일 1개 , 2*2 타일 1개, 2*1 타일 2개로 끝나는 형태일거다.

그럴경우, N개에서, N-1개의 경우의 수도 마찬가지로, 이 3가지로 끝날거다. 따라서, 재귀적인 관계가 성립함.

그래서, F(N) = F(N-1) + 2*F(N-2) 라고 할 수있음.

#TOP - down
import sys
sys.setrecursionlimit(10**6)

def sol(n):
    if n==1: return 1
    if n==2: return 3
    if DP[n] ==0:
        DP[n] = sol(n-1)+2*sol(n-2)
    return DP[n]
     
N=int(input())
DP =[0]*(N+1)
print(sol(N)%10007)