[BOJ] 11727: 2×n 타일링 2 (Python)

문제 링크

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

풀이 전략

Dynamic Programming

점화식을 세워 Bottom-up 방식으로 해결할 수 있는 간단한 동적계획법 문제입니다.

구현

if __name__ == "__main__":
    n = int(input())
    dp = [0] * (n+1)

    dp[1] = 1
    dp[2] = 3

    for i in range(3, n+1):
        dp[i] = dp[i-2]*2+dp[i-1]
    print(dp[n]%10007)