11726번: 2×n 타일링
2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.
www.acmicpc.net
내 풀이:
import sys
n= int(sys.stdin.readline())
arr=[1, 1]
for i in range(2,n+1):
arr.append(arr[i-2]+arr[i-1])
print(arr[n]%10007)
잘 모르겠어서 냅다 세어봤더니 피보나치 수열과 같아서 금방 풀었다.
i번째 경우의 수 == i-1번째 경우의 수 + i-2번째 경우의 수.
안 세고도 이 공식이 나오려면 어떻게 생각해야 했을까?
'알고리즘 PS > DP' 카테고리의 다른 글
| 백준 #1149 RGB거리 (파이썬) (0) | 2024.08.26 |
|---|---|
| DP 황금미로 (0) | 2024.06.08 |
| 백준 #9095 1, 2, 3 더하기 (1) | 2023.11.09 |
| 백준 #2839 설탕배달 (1) | 2023.10.02 |
| 백준 #1463 1로 만들기 (0) | 2023.10.02 |