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

문제

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

문제 흐름

이전에 이번 문제인 2×n 타일링을 풀고 정리한 적이 있다.
이번 문제 또한 이전의 풀이법을 참고한다면 쉽게 해결책을 찾을 수 있다.

위 그림에서 알 수 있듯이 이전에는 2×2 칸을 채우는 방법이 1×2 타일을 두개 놓는 방법 뿐이었지만, 이번에는 2×2 타일을 이용하는 방법 또한 있다.
앞에 2×1 칸을 2×1 타일을 이용해 채우는 경우 n = i-1의 값을 가져오고,
앞에 2×2 칸을 채울 때, 1×2 타일을 이용하는 경우와 2×2 타일을 이용하는 경우 n = i-2의 값을 가져온다.

따라서 memo[i]에 n = i의 경우 값을 저장한다고 할 때, 점화식은 다음과 같이 설정된다.
memo[i] = memo[i - 1] + memo[i - 2] * 2

코드

# 2×n 타일링 2
# dp

import sys
input = sys.stdin.readline

def dp (n: int):
    if n == 1:
        return 1
    elif n == 2:
        return 3
    memo = [0 for i in range(n + 1)]
    memo[1] = 1
    memo[2] = 3
    
    for i in range(3, n + 1):
        memo[i] = memo[i - 1] + memo[i - 2] * 2
    return memo[-1]

if __name__ == "__main__":
    n = int(input())
    result = dp(n)
    print(result % 10007)