https://www.acmicpc.net/problem/11726
알고리즘 분류
- 다이나믹프로그래밍
문제풀이
세로의 크기는 2로 고정되어있기때문에 n이 늘어날수록 채우는 방법의 수가 어떻게 바뀌어가는지 살펴보면 된다.
ex)
1X2타일은 =, 2X1타일은 ㅣ
n=1 ㅣ -> 1개
n=2 ㅣㅣ,= -> 2개
n=3 ㅣㅣㅣ,ㅣ=,=ㅣ -> 3개
n=4 ㅣㅣㅣㅣ,ㅣㅣ=,ㅣ=ㅣ,=ㅣㅣ,== -> 5개
n=5 ㅣㅣㅣㅣㅣ,ㅣ=ㅣㅣ,ㅣㅣ=ㅣ,ㅣㅣㅣ=,=ㅣㅣㅣ,ㅣ==,==ㅣ,=ㅣ= -> 8개
n=6 (생략) -> 13개
1->1
2->2
3->3=2+1
4->5=3+2
5->8=5+3
6->13=8+5...
소스코드
n=int(input())
d=[0]*1001
d[0]=1
d[1]=1
d[2]=2
for i in range(2,n+1):
d[i]=d[i-1]+d[i-2]
print(d[n]%10007)