문제
알고리즘
- 점화식을 구해보면 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
'CodingTest > Baekjoon' 카테고리의 다른 글
[baekjoon] 백준 14501번(파이썬): 퇴사 (0) | 2021.12.02 |
---|---|
[baekjoon] 백준 9461번(파이썬): 파도반 수열 (0) | 2021.11.30 |
[baekjoon] 백준 2193번(파이썬): 이친수 (0) | 2021.11.28 |
[baekjoon] 백준 1149번(파이썬): RGB 거리 (0) | 2021.11.27 |
[baekjoon] 백준 2156번(파이썬): 포도주 시식 (0) | 2021.11.26 |