백준 11727번 파이썬 문제풀이(DP - 2*n 타일링 2)

---

코드

n = int(input())

dp = [0, 1, 3]  # n이 2이하일때 횟수를 미리 초기화

if n > 2:
    for i in range(3, n + 1):
        dp = dp + [0] * (n - 2)
        dp[i] = (dp[i - 2] * 2) + dp[i - 1]

print(dp[n] % 10007)

-> 간단히 11726번과 비슷하게 점화식만 찾으면 된다. 그림을 그려서 n이 4일때와 5일때를 확인해보면 11과 21이 나온다. 5개 정도가 나오면 점화식을 찾을 수 있는데 (n-2)번째 * 2 + (n-1)번째 가 반복되는 것을 알 수 있다.

 

* 그림을 직접 그리면서 확인해야 하다보니 4번째가 계속 10이 나와서 결국 답을 봤다.  시간도 오래걸리는 이런 노가다 문제...