(C++) - 백준(BOJ) 16195번 : 1, 2, 3 더하기 9

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

16195번: 1, 2, 3 더하기 9

dp로 해결한 문제였습니다. 

 

풀이방법

1,2,3을 이용해 i이라는 숫자를 j개로 만들기 위한 점화식은 다음과 같습니다.

d[i][j] = d[i-1][j-1] + d[i-2][j-1] + d[i-3][j-1]

1을 사용했을 때 숫자를 1개를 소모한 경우 + 2를 사용했을 때 숫자를 1개 소모한 경우 + 3을 사용했을 때 숫자를 1개 소모한 경우라고 풀어서 쓸 수 있습니다.

 

Code(Bottom Up)

#include <bits/stdc++.h>
#define MOD 1000000009
#define ll long long
using namespace std;
ll t, n, m;
ll d[1001][1001];
int main(){
    cin >> t;
    d[1][1] = 1;
    d[2][1] = 1;
    d[2][2] = 1;
    d[3][1] = 1;
    d[3][2] = 2;
    d[3][3] = 1;
    
    for(int i = 4; i <= 1000; i++){
        for(int j = 2; j <= i; j++){
            d[i][j] += (d[i-1][j-1] % MOD + d[i-2][j-1] % MOD + d[i-3][j-1] % MOD) % MOD;
        }
    }

    while(t--){
        cin >> n >> m;
        ll ans = 0;
        for(int i = 1; i <= m; i++) ans = (ans % MOD + d[n][i] % MOD) % MOD;
        cout << ans << '\n';
    }
}

 

Code(Top Down)

#include <bits/stdc++.h>
#define MOD 1000000009
#define ll long long
using namespace std;
ll t,n,m;
ll d[1001][1001];
ll dp(ll num, ll cnt){
    if(!num && !cnt) return 1;
    if(num < 0 || cnt < 0) return 0;
    ll &ret = d[num][cnt];
    if(ret != -1) return ret;
    ret = 0;
    ret = (dp(num-1,cnt-1) % MOD + dp(num-2,cnt-1) % MOD + dp(num-3,cnt-1) % MOD) % MOD;

    return ret;
}
int main(){
    cin >> t;
    memset(d,-1,sizeof(d));
    for(int i = 1; i <= 1000; i++){
        ll a = dp(1000,i);
    }
    while(t--){
        cin >> n >> m;
        ll ans = 0;
        for(int i = 1; i <= m; i++){
            ans = (ans % MOD + dp(n,i) % MOD) % MOD;
        }
        cout << ans << '\n';
    }
}