BOJ 15988 · 1, 2, 3 더하기 3

알고리즘 분류 : 다이나믹 프로그래밍  

숫자 N을 1, 2, 3의 합으로 나타내는 방법의 수를 구해야 한다. BOJ 9095번 '1, 2, 3 더하기'에서 범위가 확장된 문제다.

• D[N] : 숫자 N을 1, 2, 3의 합으로 나타내는 방법의 수
• D[1] = 1
• D[2] = 2 (1+1, 2)
• D[3] = 4 (1+1+1, 1+2, 2+1, 3)
• D[N-1] : 마지막에 1을 더한 방법의 수
• D[N-2] : 마지막에 2를 더한 방법의 수
• D[N-3] : 마지막에 3을 더한 방법의 수

---

C++ 소스코드

#include <cstdio>

int n;
long long d[1000001];

void solve() {
    d[1] = 1, d[2] = 2, d[3] = 4;
    for (int i=4; i<1000001; i++) {
        d[i] = d[i-1]+d[i-2]+d[i-3];
        d[i] %= 1000000009;
    }
}

int main() {
    int t;
    scanf("%d", &t);
    solve();
    while (t--) {
        int n;
        scanf("%d", &n);
        printf("%lld\n", d[n]);
    }
    return 0;
}

---

Python 3 소스코드

d = [0, 1, 2, 4]
for i in range(4, 1000001):
    d.append((d[i-1]+d[i-2]+d[i-3])%1000000009)
for _ in range(int(input())):
    print(d[int(input())])

---

참고

• 백준 온라인 저지 : BOJ 15988
• 1, 2, 3 더하기