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

문제링크

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

11727번: 2×n 타일링 2

 

코드

import sys
input = sys.stdin.readline
 
n = int(input())
d = [0]*1001
 
d[1]=1
d[2]=3
 
for i in range(3, n+1):
    d[i] = (d[i-1] + 2*d[i-2])%10007
 
print(d[n])

 

Point

- 다이나믹프로그래밍으로 접근

 Subproblem 만족 & Optimal Substructure 

 

- 풀이 방법:

d(n) = 2*n을 채우는 방법의 수
n번째에서 새롭게 할 수 있는 행동은 
(1) d(n-1)에 추가로 1*2타일 1개 배치하기
(2) d(n-2)에 추가로 2*1타일 2개 배치하거나 OR 2*2타일 1개 배치하기

--> d(n) = d(n-1) + 2*d(n-2) 가 성립, d(1) = 1 , d(2) = 3