[백준] 11726 : 2xn 타일링 - Python(파이썬)

[Silver 3] 11726 : 2xn 타일링 - Python

 

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

11726번: 2×n 타일링

 

---

설명

2xn인 사각형을 1x2인 블럭과 2x1인 블럭으로 2xn 사각형을 채울 수 있는 총 경우의 수를 구하는 문제이다

2xn인 경우 n = 1 인 경우부터 차례로 그려가며 생각해보면 알기 편하다

n = 1  => 1가지

n = 2  => 2가지

n = 3  => 3가지

n = 4  => 5가지

          .

          .

 

즉 n과 관련된 점화식을 찾을 수 있다.

점화식 : dp[N] = dp[N-1] + dp[N-2]

 

N = int(input())
res = 0

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

for i in range(N+1):
    if i == 0:
        dp[i] = 0
    
    elif i == 1:
        dp[i] = 1

    elif i == 2:
        dp[i] = 2

    else:
        dp[i] = dp[i-1] + dp[i-2]

print(dp[N] % 10007)