다이나믹 프로그래밍 - 백준 15990 [Python]

Problem)

https://www.acmicpc.net/problem/15990

15990번: 1, 2, 3 더하기 5

 

Solution)

어떤 조건이 나타났을 때, 그 조건을 점화식에 넣어버리면 된다.

 

따라서, n-1로 끝났을 때 마지막에 어떤수를 사용했는지 정의하는 것을 추가해야 한다.

 

D[i][j] = i를 1,2,3의 합으로 나타내는 방법의 수, 마지막에 사용한 수는 j

i-1을 만든 경우 = D[i-1][2] + D[i-1][3]

i-2를 만든 경우 = D[i-2][1] + D[i-2][3]

i-3을 만든 경우 = D[i-3][1] + D[i-3][2]

 

따라서 정답은 D[n][1] + D[n][2] + D[n][3]이 된다.

 

초기화 같은 경우에도 각각 초기화를 해주어야 한다.

Answer)

limit = 100000
d = [[0]*4 for _ in range(limit+1)]
mod = 1000000009


for i in range(1, limit+1):
    if i-1 >= 0:
        d[i][1] = d[i-1][2] + d[i-1][3]
        if i == 1:
            d[i][1] = 1
    if i-2 >= 0:
        d[i][2] = d[i-2][1] + d[i-2][3]
        if i == 2:
            d[i][2] = 1
    if i-3 >=0:
        d[i][3] = d[i-3][1] + d[i-3][2]
        if i == 3:
            d[i][3] = 1
    d[i][1] %= mod
    d[i][2] %= mod
    d[i][3] %= mod

t = int(input())
for _ in range(t):
    n = int(input())
    print(sum(d[n])%mod)