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

1. 문제 주소

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

2. 문제

정수 n을 1, 2, 3의 합으로 나타내는 방법의 수를 출력하는 문제이다. n을 나타내는 방법은 n-1을 나타내는 방법에서 1을 더하고 n-2를 나타내는 방법에서 2를 더하고 n-3을 나타내는 방법에서 3을 더하면 된다. 따라서 n을 나타내는 방법의 수는 n-1, n-2, n-3을 나타내는 방법을 모두 더해주면 된다.

3. 소스 코드

#include <iostream>
using namespace std;
long long divide = 1000000009LL;
long long result[1000001];
int main() {
    int t;
    cin >> t;
    result[0] = 1; result[1] = 1; result[2] = 2;
    for (int i = 3; i <= 1000000; i++) {
        result[i] = (result[i - 1] + result[i - 2] + result[i - 3]) % divide;
    }
    while (t--) {
        int n;
        cin >> n;
        cout << result[n] << '\n';
    }
    return 0;
}