[BOJ] 백준 11726 2xn 타일링 Python

11726번: 2×n 타일링

문제풀이
n의 범위는 1 <= n <= 1,000이다
따라서 n==1000일 경우엔 수많은 경우의 수가 존재하기 때문에 DP가 이 문제에 적합하다고 생각했다.
DP문제가 항상 그렇듯 초기값을 정하고 나선 항상 그 초기값 케이스에 대한 경우 처리를 따로 해주어야한다. 예를 들어 n == 2일때와 같은 상황을 말한다.
경우의 수를 구하는 문제기 때문에 n이 작을때는 그림을 그려도 경우의 수가 많지 않을거라고 생각해 그림을 그렸더니 패턴을 찾을 수 있었다. 이는 아래의 그림과 같다.

n이 1,2,3,4일때의 타일이 채워지는 경우의 수

DP 배열과 점화식

---

Code

from sys import stdin

input = stdin.readline
div = 10007


def solve():
    n = int(input())
    dp = [0] * n
    dp[0] = 1
    if n >= 2:
        dp[1] = dp[0] + 1
    if n >= 3:
        dp[2] = dp[1] + 1
    for i in range(3, n):
        dp[i] = dp[i - 1] + dp[i - 2]
    print(dp[-1] % div)


solve()