boj 15990 1, 2, 3 더하기 5

 

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

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

1, 2, 3 더하기 4 문제를 푼 다음이어서 그런지 점화식을 빠르게 찾았습니다.

 

이 문제는 식이 1로 끝나는 경우, 2로 끝나는 경우, 3으로 끝나는 경우로 나누어 해결합니다.

1 → 1

2 → 2

3 → 2+1, 1+2, 3

 

이제 점화식을 세워보면,

dp[0][N] (N을 나타내는 방법 중 1로 끝나는 방법의 수)

= dp[1][N - 1] + dp[2][N - 1] (N - 1에서 2로 끝나는 방법 + 3으로 끝나는 방법)

 

dp[1][N] (N을 나타내는 방법 중 2로 끝나는 방법의 수)

= dp[0][N - 2] + dp[2][N - 2] (N - 2에서 1로 끝나는 방법 + 3으로 끝나는 방법)

 

dp[2][N] (N을 나타내는 방법 중 3로 끝나는 방법의 수)

= dp[0][N - 3] + dp[1][N - 3] (N - 3에서 1로 끝나는 방법 + 2로 끝나는 방법)

 

이렇게 되겠습니다.

 

 

#include <iostream>
#define MOD 1000000009
using namespace std;
 
int dp[3][100001];
 
void init() {
    dp[0][1] = 1;
    dp[1][2] = 1;
    dp[0][3] = 1;
    dp[1][3] = 1;
    dp[2][3] = 1;
    for (int i = 4; i <= 100000; i++) {
        dp[0][i] = (dp[1][i - 1] + dp[2][i - 1]) % MOD;
        dp[1][i] = (dp[0][i - 2] + dp[2][i - 2]) % MOD;
        dp[2][i] = (dp[0][i - 3] + dp[1][i - 3]) % MOD;
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    init();
    int tc, N;
    cin >> tc;
    while (tc--) {
        cin >> N;
        cout << ((dp[0][N] + dp[1][N]) % MOD + dp[2][N]) % MOD << '\n';
    }
 
    return 0;
}