반응형
https://www.acmicpc.net/problem/15992
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';
}
}
'Algorithm > DP(Dynamic Programing)' 카테고리의 다른 글
(C++) - 백준(BOJ) 15989번 : 1, 2, 3 더하기 4 (0) | 2021.05.26 |
---|---|
(C++) - 백준(BOJ) 16195번 : 1, 2, 3 더하기 9 (0) | 2021.05.25 |
(C++) - 프로그래머스(Summer/Winter Coding(~2018)) : 스티커 모으기(2) (0) | 2021.05.24 |
(C++) - 프로그래머스(연습문제) : 멀리 뛰기 (0) | 2021.05.18 |
(C++) - 백준(BOJ) 2096번 : 내려가기 (0) | 2021.05.11 |