[15990] 1, 2, 3 더하기 5

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

15990번: 1, 2, 3 더하기 5

<문제>

dp[i][j] : i의 수를, j를 마지막으로 사용하여 만드는 경우의 수

 

연속적으로 수를 사용할 수 없으므로, 두 번째 인덱스가 동일한 것만 제외하고

dp값을 2개씩 참조하도록 점화식을 구성하면 된다.

<소스코드>

#include <bits/stdc++.h>
using namespace std;
const int MOD = 1000000009;
int t, n;
long long dp[100001][4];
int main(void) {
    int i, j;
    dp[1][1] = 1;
    dp[2][2] = 1;
    dp[3][1] = dp[3][2] = dp[3][3] = 1;
    for (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;
    }
    cin >> t;
    while (t--) {
        cin >> n;
        cout << (dp[n][1] + dp[n][2] + dp[n][3]) % MOD << '\n';
    }
    return 0;
}