[Python] 백준 #11727 - 2×n 타일링 2

문제

11727번: 2×n 타일링 2

2×n 직사각형을 1×2, 2×1과 2×2 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×17 직사각형을 채운 한가지 예이다.

www.acmicpc.net

n = int(input())
d = [0]*1001
d[1] = 1
d[2] = 3

for i in range(3,1001):
    d[i] = (d[i-1] + 2*d[i-2])%10007
print(d[n])

경우의 수를 다 구해보면된다.

d[n-1]일떄는 2*1 타일이 붙을 수 있다. (d[n]+=d[n-1])
d[n-2]일때는 1*2 타일 2개, 2*2타일 두개가 붙을 수 있다. d[n-2]의 타일들에 *2를 해주면된다. (d[n]+=d[n-2]*2)
이때 2*1 타일 두개는 d[n-1]에 포함되므로 패스한다.

[다른사람 풀이]

a=b=1
for i in range(int(input())):
   a,b=b,2*a+b
print(a%10007)

이렇게도 풀 수 있다.