알고리즘 PS/DP
백준 #11726번 2xn 타일링[파이썬]
explorer999
2024. 2. 1. 15:15
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번째 경우의 수.
안 세고도 이 공식이 나오려면 어떻게 생각해야 했을까?