https://www.acmicpc.net/problem/11726
11726번: 2×n 타일링
2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.
www.acmicpc.net
n = int(input())
d = [0] * 1001
d[1] = 1
d[2] = 2
for i in range(3,n+1):
d[i] = (d[i-1] + d[i-2]) % 10007
print(d[n])[다이나믹 프로그래밍]
문제에서 주어진대로 값을 확인해보면 피보나치와 유사한 형태의 점화식이 세워지는 것을 알 수 있다.
-> d[i] = d[i-1] + d[i-2]
'Algorithm > 백준' 카테고리의 다른 글
| 백준 1065번(Python) : 한수 (0) | 2021.03.01 |
|---|---|
| 백준 11727번(Python) : 2 x n 타일링 2 (0) | 2021.02.26 |
| 백준 11048번(Python) : 이동하기 (0) | 2021.02.24 |
| 백준 1212번(Python) : 8진수 2진수 (0) | 2021.02.24 |
| 백준 13301번(Python) : 타일 장식물 (0) | 2021.02.21 |
