[baekjoon] 백준 11727번(파이썬): 2×n 타일링 2

문제

11727번: 2×n 타일링 2

알고리즘

- 점화식을 구해보면 n = 1일 때, 1이고 n = 2일 때, 3이고 n = 3일 때, 5이고 n = 4일 때, 11인 것을 확인할 수 있다.

- 점화식 : dp[n] = dp[n - 1] + (dp[n - 2] * 2)

코드

import sys

n = int(sys.stdin.readline())
dp = [0] * 1001
dp[1] = 1
dp[2] = 3

# 반복문을 통해 점화식을 코드로 수행
# n = 1일때 1가지, n = 2일때 3가지, n = 3일때 5가지, n = 4일때 11가지
# f(n) = (f(n - 2) * 2) + f(n - 1)
for i in range(3, n + 1):
    dp[i] = (dp[i - 2] * 2) + dp[i - 1]
print(dp[n] % 10007)

github

GitHub - junjange/CodingTest: 내가 푼 코딩 테스트 문제와 해결법