(Python) - BOJ(11726번) : 2 x n 타일링

https://www.acmicpc.net/problem/11726

11726번: 2×n 타일링

---

• 문제 : 

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

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

 

 

 

---

• 풀이 :

예전에 풀었던 문제와 똑같은 문제이다. 그림을 그려가며 규칙을 찾는데 

 

f(n) = f(n-2) + f(n-1)이라는 점화식이 도출되었다 이를 구현하면 끝이다.

 

 

 

---

• 소스코드 : 

import sys
input =sys.stdin.readline
 
 
if __name__ == "__main__":
    N = int(input())
    dp = [0] * (N+2)
    dp[1] = 1
    dp[2] = 2
    if N > 2:
        for i in range(3,N+1):
            dp[i] += dp[i-1]+dp[i-2]
    print(dp[N]%10007)