1, 2, 3 더하기 3 15988

문제

접근 방법

1, 2, 3 더하기에서 범위가 늘어났다.
미리 구하기보다는 필요할 때 구하는 방식으로 접근하였다.
(미리 구하려면 1,000,000의 크기만큼 돌아야 한다)

코드

#include <iostream>
using namespace std;
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int T, min = 4;
    cin >> T;
    long long dp[1000001];
    dp[1] = 1;
    dp[2] = 2;
    dp[3] = 4;
    while (T--)
    {
        long long n;
        cin >> n;
        for (int i = min; i <= n; ++i)
        {
            dp[i] = (dp[i - 3] + dp[i - 2] + dp[i - 1]) % 1000000009;
        }
        cout << dp[n] << "\n";
        if (min < n)
        {
            min = n + 1;
        }
    }
    return 0;
}

풀이

이미 구해놓은 값은 다시 구할 필요가 없으니 min이라는 변수를 활용하여 건너뛰었다.

예전에 배열 관련해서 문제가 있었다고 하였다. 백준에서는 정상적으로 작동하지만 내 환경에서는 종료가 되는 것을 말이다.
찾아보니 함수 내에서 크기가 큰 배열을 선언하여 스택 크기 제한에 걸리는 것이다. (함수의 지역변수, 매개변수는 스택 영역이다)

전역변수로 선언하면 해결되는 문제였다.
이번 문제는 지역변수로 선언했지만 다음부터는 크기가 커서 문제가 생기면 전역변수로 해결해야겠다.