[백준/c++] BOJ 15990 - 1, 2, 3 더하기 5

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

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

 

문제 설명

정수 n을 1, 2, 3의 합으로 나타낸다. 단, 같은 수를 두 번 이상 연속해서 사용하면 안 된다.

1, 2, 3의 합으로 나타내는 방법의 수를 1,000,000,009로 나눈 나머지를 출력한다.

n (1 <= n <= 100,000)

해결

직전에 사용했던 수는 사용하지 못하므로, 2차원 배열을 사용했다.

 

dp[n][1] : n을 만들기 위해 마지막으로 1을 더한 수

dp[n][2] : n을 만들기 위해 마지막으로 2를 더한 수

dp[n][3] : n을 만들기 위해 마지막으로 3을 더한 수

 

다음과 같은 점화식을 구할 수 있었다.

dp[n][1] = dp[n-1][2] + dp[n-1][3]

dp[n][2] = dp[n-2][1] + dp[n-2][3]

dp[n][3] = dp[n-3][1] + dp[n-3][2]

 

코드

#include<bits/stdc++.h>
#define x first
#define y second
#define INF 1e9
using namespace std;

int n, m;
long long dp[100005][5];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

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

    cin >> n;
    while (n--) {
        cin >> m;

        for (int i = 4; i <= m; 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;
        }
        cout << (dp[m][1] + dp[m][2] + dp[m][3]) % 1000000009 << "\n";
    }
}