[backjoon] 11726 2 X n 타일링 (python)

문제 11726번: 2Xn 타일링

Dynamic Programming

2×n 크기의 직사각형을 1×2, 2×1 타일로 채우는 방법의 수를 구하는 프로그램을 작성하시오.

아래 그림은 2×5 크기의 직사각형을 채운 한 가지 방법의 예이다.

예제 입력

2

예제 출력

2

---

문제 풀이

입력 N	방법의 수
1	1
2	2
3	3
4	5
5	8
6	13

위의 표를 통해 dp[N] = dp[N-1]+dp[N-2]점화식을 떠올릴 수 있다.
피보나치와 유사함!

전체 코드

import sys
input = sys.stdin.readline

n = int(input())

dp = [0 for _ in range(n+1)]

if n <= 3 : print(n)
else : 
	dp[1] = 1
	dp[2] = 2
	for i in range(3, n+1):
		dp[i] = dp[i-1] + dp[i-2]

	print(dp[i]%10007)
    # 10007을 나누어주는 이유는
    # 문제에서 첫째 줄에 2×n 크기의 직사각형을 채우는 방법의 수를 
    # 10,007로 나눈 나머지를 출력한다.라고 했기 때문이다!

출처 백준 (boj) 파이썬 - 11726 번 : 2 x n 타일링 (DP)