[Algorithm]Baekjoon 15988번 : 1,2,3 더하기 3

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

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

#define MAX_NUM 1000000009;
 
long long dpArray[1000001];
 
long dp(int n)
{
    for (int i = 5; i <= n; i++)
    {
        dpArray[i] = (dpArray[i - 1] + dpArray[i - 2] + dpArray[i - 3]) % MAX_NUM;
    }
 
    return dpArray[n];
}
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    int num = 0;
    int temp = 0;
    vector<int> result;
    dpArray[0] = 0;
    dpArray[1] = 1;
    dpArray[2] = 2;
    dpArray[3] = 4;
    dpArray[4] = 7;
 
    cin >> num;
 
    for (int i = 0; i < num; i++)
    {
        cin >> temp;
        result.push_back(dp(temp));
    }
 
    for (auto temp : result)
    {
        cout << temp << endl;
    }
}

바로 이전문제인 1,2,3더하기 문제랑 동일한 문제인데 거기에 약간의 추가조건만 달린 문제이다.

n값이 최대 100만에다가 결과값에 1000000007을 나눈 나머지를 출력하는 문제이다.

은근히 이런 문제들이 꽤 나오는것같다.

과감하게 데이터타입을 long이나 long long으로 해주자