[algorithm] 백준 - 1,2,3 더하기 5

DP문제이다.

n을 1, 2, 3의 합으로 나타내는 방법의 수를 구하는 것이다.

여기서 중요한 점은 같은 수를 두 번 이상 연속해서 사용하면 안된다는 것이다.

그렇기에 뒷자리수를 함께 기록해야한다.

 

뒷자리수가 1일 때 다음 수는 2나 3이,

2이면 다음 수는 1이나 3,

3이면 다음 수는 1이나 2 여야한다.

이것을 점화식으로 표현해보자면,

dp[i][1] = dp[i - 1][2] + dp[i - 1][3];
dp[i][2] = dp[i - 2][1] + dp[i -2][3];
dp[i][3] = dp[i - 3][1] + dp[i - 3][2];

전체 코드는 이렇다.

// 1, 2, 3 더하기 5
#include <iostream>
using namespace std;
int main(void){
    long long test,n, dp[100001][4];
    cin >> test;
    dp[1][1] = 1; dp[1][2] = 0; dp[1][3] = 0;
    dp[2][1] = 0; dp[2][2] = 1; dp[2][3] = 0;
    dp[3][1] = 1; dp[3][2] = 1; dp[3][3] = 1;
    for(int i = 4; i < 100001; i++){
        dp[i][1] = (dp[i - 1][2] + dp[i - 1][3])% 1000000009;
        dp[i][2] = (dp[i - 2][1] + dp[i -2][3])% 1000000009;
        dp[i][3] = (dp[i - 3][1] + dp[i - 3][2])% 1000000009;
    }
    while(test--){
        cin >> n;
        cout << (dp[n][1] + dp[n][2] + dp[n][3]) % 1000000009 << "\n";
    }
}