[백준] 15990번 : 1, 2, 3 더하기 5

문제

 

---

풀이

 

myunji.tistory.com/318?category=1154147

[백준] 15988번 : 1, 2, 3 더하기 3

이 문제에서 숫자의 연속 등장을 제외해야 하는 문제이다.

 

숫자의 연속 등장을 제외하기 위해선 마지막에 등장한 숫자가 무엇인지 저장해야 한다.

1, 2, 3 더하기니까 마지막에 등장할 수 있는 숫자 역시 1, 2, 3이다.

 

dp[i][j]에 숫자 i를 1, 2, 3의 합으로 나타낸 경우 중 j+1로 끝나는 것의 수를 저장할 것이다.

그니까 dp[3][0]이라면 숫자 3을 1, 2, 3의 합으로 나타낸 경우 중 1로 끝나는 것의 개수가 될 것이다.

이 경우에 해당하는 것은 2+1 하나이므로 dp[3][0]=1이다.

 

그럼 점화식을 다시 세워보면 i가 4보다 크거나 같을 때,

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

라고 할 수 있다.

---

소스코드

 

#include <iostream>

using namespace std;

const int DIVISOR = 1000000009;
long long dp[1000001][3];

void dpSum() { //dp[i-1]+1, dp[i-2]+2, dp[i-3]+3
    dp[1][0] = dp[2][1] = dp[3][0] = dp[3][1] = dp[3][2] = 1;

    for (int i = 4; i <= 1000000; i++) {
        dp[i][0] = (dp[i - 1][1] + dp[i - 1][2]) % DIVISOR;
        dp[i][1] = (dp[i - 2][0] + dp[i - 2][2]) % DIVISOR;
        dp[i][2] = (dp[i - 3][0] + dp[i - 3][1]) % DIVISOR;
    }
}

int main() {
    int T, n;

    dpSum();
    cin >> T;
    for (int i = 0; i < T; i++) {
        cin >> n;
        cout << (dp[n][0] + dp[n][1] + dp[n][2]) % DIVISOR << '\n';
    }
}