2×n 타일링 2 풀이

문제 링크: https://www.acmicpc.net/problem/11727

백준 알고리즘 기초 1/2 400에서 3번째 - 11727번 2×n 타일링 2를 풀어보았다.

 

풀이: i번째=i-1번째+i-2번째*2라는 점화식을 잘 아는 게 중요한 거 같다.

 

C++

 

Python

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

Java