[C++/백준 15990번] 1, 2, 3 더하기 5

 

 

 

2차원 배열 점화식을 이용하는 문제. 점화식을 이용한 dp 를 하는 것에 익숙해져야겠다.

 

 

#include <iostream>
#include <algorithm>
using namespace std;

#define MOD 1000000009

int arr[1001];
int dp[100001][4];

void DP()
{

    dp[1][1] = dp[2][2] = dp[3][1] = dp[3][2] = dp[3][3] = 1;

    for (int i = 4; i <= 100000; i++)
    {
        dp[i][1] = (dp[i - 1][2] + dp[i - 1][3]) % MOD;

        dp[i][2] = (dp[i - 2][1] + dp[i - 2][3]) % MOD;

        dp[i][3] = (dp[i - 3][1] + dp[i - 3][2]) % MOD;

    }


}


int main() {

    int N;
    cin >> N;

    DP();

    for (int i = 0; i < N; i++)
    {
        int input;
        cin >> input;

        cout << (dp[input][1] + dp[input][2] + dp[input][3]) % MOD;
    }


   


    return 0;
}