Study/코딩 테스트
2021.2.10 [백준] 2xn 타일링
NOredstone
2021. 2. 10. 13:56
다이나믹 프로그래밍 알고리즘
Q
11726번: 2×n 타일링
2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.
www.acmicpc.net
A
점화식을 세우는 것이 중요하다. n-1, n-2번째를 생각하였을때의 점화식으로 답이 안나오면 n = 1일때부터 차근차근 생각해보자.
코드
import sys
n = int(sys.stdin.readline())
d = [0] * 1001
d[1] = 1
d[2] = 2
for i in range(3, 1001):
d[i] = d[i-1] + d[i-2]
print(d[n] % 10007)