[BOJ/python] 11726: 2×n 타일링

문제

✔️ silver 3
다이나믹 프로그래밍

문제 흐름

이 문제의 점화식은 다음과 같이 찾았다.
n=1과 n=2인 경우를 초기값으로 다음과 같이 계속 반복하여 다음 값을 구할 수 있다.

코드

# 2×n 타일링
# dp

import sys
input = sys.stdin.readline

def dp(n: int):
    d = [0 for i in range(n + 1)]
    if n == 1:
        return 1
    elif n == 2:
        return 2
    d[1] = 1
    d[2] = 2

    for i in range(3, n + 1):
        d[i] = d[i - 1] + d[i - 2]

    # print(d)
    return d[-1]


if __name__ == "__main__":
    n = int(input())

    result = dp(n) % 10007
    print(result)

마무리

직접 그려가며 찾느라 노가다를 살짝 했지만 패턴을 찾기 어려운 문제는 아니었다.