1, 2, 3 더하기 5 15990

문제

접근 방법

1의 경우 1
2의 경우 2
3의 경우 1+2, 2+1, 3
4의 경우 1+3, 1+2+1, 3+1
5의 경우 1+3+1, 2+3, 2+1+2, 3+2
6의 경우 1+2+1+2, 1+2+3, 1+3+2, 2+1+2+1, 2+1+3, 2+3+1, 3+1+2, 3+2+1
7의 경우 1+2+1+3, 1+2+3+1, 1+3+1+2, 1+3+2+1, 2+1+1+3, 2+1+3+1, 2+3+2, 3+1+2+1, 3+1+3

	1	2	3	4	5	6	7
1	1	0	1	2	1	3	4
2	0	1	1	0	2	3	3
3	0	0	1	1	1	2	2
답	1	1	3	3	4	8	9

각 숫자 뒤에는 다른 숫자가 붙어야 한다.
1 뒤에는 ( 2, 3 ) 2 뒤에는 ( 3, 1 ) 3 뒤에는 ( 1, 2 )가 붙는다.
즉 N의 1로 시작하는 경우는 N-1의 2와 3으로 시작하는 경우를 합친 것이다.
이후 N의 1~3으로 시작하는 경우를 다 합치면 n을 1~3의 합으로 나타내는 방법의 수가 나온다.

코드

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

    return 0;
}

풀이

DP[0][N]=DP[1][N-1]+DP[2][N-1]
DP[1][N]=DP[0][N-2]+DP[2][N-2]
DP[2][N]=DP[0][N-3]+DP[1][N-3]
이런 식의 식이 나온다고 보면 된다.
마지막에 sum을 int로 해줬다가 틀렸다.
당연히 int 범위 밖을 나갈 수 있기에 long long으로 해줬어야 했는데 허무하게 틀린 것 같다.