백준 1904 : 문제링크
문제유형 :
- 동적 프로그래밍
설명
동적 프로그래밍 문제를 풀기 위해서는 점화식(인접한 항들 사이의 관계식)을 세워야 한다.
D[i] = 수열의 길이가 i일 때의 경우에 수
D[i] = D[i-1] + D[i-2]
풀이
1
2
3
4
5
6
7
8
9
10n = int(input())
dp = [0] * 1000001
dp[1] = 1
dp[2] = 2
for i in range(3, n+1)
dp[i] = (dp[i - 2] + dp[i - 1]) % 15746
print(d[[n]])