[백준15988] 1, 2, 3 더하기 3

문제

---

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

15988번: 1, 2, 3 더하기 3

 

생각의 흐름

---

dp[i]에 i를 1, 2, 3 더하기로 i를 만들 수 있는 경우의 수를 저장한다. 동적 프로그래밍을 위한 점화식은 dp[i]=dp[i-1] + dp[i-2] + dp[i-3]이 된다. 이처럼 이전의 3항까지만을 더해주는 이유는 1, 2, 3으로 만드는 수이기 때문에 3만큼 작은 수를 만들 수 있는 가짓수를 더해주면 3이라는 수로 그 부족분을 보충해줄 수 있기 때문이다.

 

코드

---

# 백준 15988

t = int(input())
dp = [0]*(1000001)
dp[1],dp[2],dp[3]=1,2,4
for i in range(4, 1000001):
    dp[i] = ((dp[i-1] + dp[i-2]) %1000000009 + dp[i-3]) % 1000000009
for _ in range(t):
    n = int(input())
    if n==1:
        print(dp[1])
        continue
    elif n==2:
        print(dp[2])
        continue
    elif n==3:
        print(dp[3])
        continue
    print(dp[n])