1, 2, 3 더하기 8 15993

문제

접근 방법

1, 2, 3 더하기 7하고 유사하다고 생각했다.
짝수가 되려면 홀수인 경우에 1개를 붙이면 된다. 반대의 경우도 성립한다.
4까지의 과정을 예시로 들자.
1 홀수 1
2 홀수 2 짝수 1+1
3 홀수 1+1+1 3 짝수 2+1 1+2
4 홀수 2+1+1 1+2+1 1+1+2 짝수 1+1+1+1 1+3 2+2 3+1
이전 단계들의 홀수가 짝수에 사용되고 짝수가 홀수에 사용되는 것을 볼 수 있다.

코드

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

풀이

홀수, 짝수인 경우에 1, 2, 3을 붙이면 짝수, 홀수가 된다. 그러한 점을 이용해서 1, 2, 3만큼 떨어진 곳에 홀수, 짝수 값을 가져와 1, 2, 3을 붙이고 짝수, 홀수로 만들어 사용하는 것이다.
1, 2, 3 더하기를 7까지 풀었다면 7과 비슷한 원리인 8은 쉬웠을 것이다.