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

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

15991번: 1, 2, 3 더하기 6

 
int t, n;
vector<int> answers;
long long dp[100001] = { 0 };
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> t;
    int maxN = 0;
 
    while (t--)
    {
        cin >> n;
 
        maxN = max(maxN, n);
        answers.push_back(n);
    }
 
    dp[1] = 1;
    dp[2] = 2;
    dp[3] = 2;
    dp[4] = 3; // 특이케이스라 + 1
    dp[5] = 3;
    dp[6] = 6; // 특이케이스라 +1
 
    for (int i = 7; i <= maxN; ++i)
    {
        dp[i] = (dp[i - 2] + dp[i - 4] + dp[i - 6]) % 1000000009;
    }
 
    for (int i = 0; i < answers.size(); ++i)
    {
        printf("%d\n", dp[answers[i]]);
    }
}
 
 

 

이번엔 1,2,3 조합이 대칭을 이뤄야 한다고 한다.

접근은 잘 접근했었는데, 특이케이스에 대한 부분을 알아내지 못해서 다른사람 풀이를 봤다.

4 와 6이 그러한데, 7부터는 i-2값에 1로 양쪽을 감싸고, i-4값을 2로 양쪽을 감싸고, i-6값을 3으로 양쪽을 감싼게 정답이 된다.

근데 4같은 경우는, '2 2' 라는 특이케이스가 존재하고 6같은 경우에도 '3 3'이라는 특이케이스가 존재한다.

딱 이경우 빼고는 잘 작동한다.