[백준] 11726번: 2×n 타일링 타일링 파이썬

PS/DP

3급우사기 2024. 3. 4. 02:22

11726번: 2×n 타일링

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오. 아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

www.acmicpc.net

코드는 진짜 간단한데

점화식을 생각 못해냄...

난 바보야..

풀이

맨 왼 쪽 칸이 1X2 직사각형인 경우 D[i-1]

맨 왼 쪽 칸이 2X1 직사각형 2 개인 경우 D[i-2]

합치면

2Xi 직사각형을 채우는 경우의 수 D[i]

n = int(input())
D = [0 for _ in range(n+2)]
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])