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

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

15992번: 1, 2, 3 더하기 7

dp 문제였습니다. top-down으로 해결했습니다.

 

풀이방법

 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

#include <bits/stdc++.h>
#define MOD 1'000'000'009
#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;
        cout << d[n][m] << '\n';
    }
}