[BOJ/Python3] 11726번 2xn 타일링

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

알고리즘 분류
다이나믹 프로그래밍

def tiling(num):
    dp[num] = dp[num-1] + dp[num-2]

n = int(input())
dp = [0] * (n+1)

dp[0] = 1
dp[1] = 2
if n > 2:
    for i in range(2, n):
        tiling(i)

print(dp[n-1] % 10007)

문제풀이

n=1, 출력=1 / n=2, 출력=2 / n=3, 출력=3 / n=4, 출력 = 5 ...
피보나치 수열임을 확인첫 수를 1, 두 번째 수를 2로 두는 피보나치 수열을 만드는 알고리즘을 사용하여 해결왜 피보나치 수열인가?
2 x n 크기의 직사각형을 조건에 맞게 채우는 경우의 수는
1) 맨 앞에 2 x 1(세로) 블럭을 채우고 시작하는 경우의 수 = 2 x (n-1) 크기의 직사각형을 채우는 경우의 수
2) 맨 앞에 1 x 2(가로) 블럭 두 개를 채우고 시작하는 경우의 수 = 2 x (n-2) 크기의 직사각형을 채우는 경우의 수
로 나눌 수 있다. 각각 n-1, n-2인 경우에 해당하므로 피보나치 수열을 따른다.