[백준 15990] 1, 2, 3 더하기 5, C++

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

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

 본 문제는 입력된 숫자를 1, 2, 3의 합으로 표현할 수 있는 경우의 수를 구하는 문제다. 예를 들어 7이 입력되었을 때, (합이 6이 되는 경우의 수), (합이 5가 되는 경우의 수), (합이 4가 되는 경우의 수)에 1, 2, 3을 더해서 구할 수 있다. 동일한 계산을 여러 번 해야 하며, 큰 문제를 작은 문제로 해결할 수 있기 때문에 DP로 문제를 해결할 수 있다. 문제의 조건 중 같은 수를 두 번 이상 연속해서 사용하면 안 되기 때문에, n의 합의 마지막 자릿수가 1, 2, 3인 경우로 나누어야 하며, 이때, 연속되지 않는 경우의 수만 더해야 한다. 따라서, 2차원 배열을 이용하여 점화식을 d[n][x] = d[n-x][y] + d[n-x][z] (단, x, y, z는 서로 다른 자연수)로 정의할 수 있다.

1. d[n][1] = d[n-1][2] + d[n-1][3] (단, n이 1보다 클 경우)
2. d[n][2] = d[n-2][1] + d[n-2][3] (단, n이 2보다 클 경우)
3. d[n][3] = d[n-3][1] + d[n-3][2] (단, n이 3보다 클 경우)
4. d[n][1] + d[n][2] + d[n][3]의 결과 출력

Top-down

#include <cstdio>
 
using namespace std;
 
long long d[100001][4] = {0};
const long long Mod = 1000000009LL;
 
long long cal(int n, int i) {
    if (n < 0) return 0;
    if (n == i) return 1;
    if (d[n][i]) return d[n][i];
    if (i == 1) {
        d[n][i] = cal(n-1, 2) + cal(n-1, 3);
        d[n][i] %= Mod;
    }
    else if (i == 2) {
        d[n][i] = cal(n-2, 1) + cal(n-2, 3);
        d[n][i] %= Mod;
    }
    else if (i == 3) {
        d[n][i] = cal(n-3, 1) + cal(n-3, 2);
        d[n][i] %= Mod;
    }
    return d[n][i];
}
 
int main() {
    int t;
    scanf("%d", &t);
    for (int i = 1; i <= 3; i++) {
        cal(100000, i);
    }
    while (t--) {
        int n;
        scanf("%d", &n);
        printf("%lld\n", ( cal(n, 1) + cal(n, 2) + cal(n, 3) )%Mod) ;
    }
}

 

Bottom-up

#include <cstdio>
 
using namespace std;
 
long long d[100001][4];
const long long Mod = 1000000009LL;
int main() {
    int n;
    scanf("%d", &n);
    d[1][1] = 1;
    d[2][2] = 1;
    d[3][3] = 1;
    for (int i = 1; i <= 100000; i++) {
        if (i > 1) {
            d[i][1] = d[i-1][2] + d[i-1][3];
            d[i][1] %= Mod;
        }
        if (i > 2) {
            d[i][2] = d[i-2][1] + d[i-2][3];
            d[i][2] %= Mod;
        }
        if (i > 3) {
            d[i][3] = d[i-3][1] + d[i-3][2];
            d[i][3] %= Mod;
        }
    }
    
    while (n--) {
        int tmp;
        scanf("%d", &tmp);
        printf("%lld\n", (d[tmp][1] + d[tmp][2] + d[tmp][3]) % Mod);
    }
    return 0;
}