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

문제 출처: https://www.acmicpc.net/problem/15988

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

arr[i] = arr[i-1] + arr[i-2] + arr[i-3] (i>3) 의 점화식을 세울 수 있다. 나머지 연산을 적절하게 해주어 오버플로우가 나지 않게 한 뒤 출력하면 된다.

#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include <string>

using namespace std;

long long arr[1000001];


int N;


int main() {
    ios::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);

    arr[1] = 1;
    arr[2] = 2;
    arr[3] = 4;

    for (int i = 4; i <= 1000000; i++) {
        long long temp= arr[i - 1] % 1000000009 + arr[i - 2] % 1000000009 + arr[i - 3] % 1000000009;
        arr[i] = temp % 1000000009;
    }

    int T;
    cin >> T;

    while (T--) {
        cin >> N;
        cout << arr[N] << '\n';
    }
    
    

}