728x90
https://www.acmicpc.net/problem/2294
문제
n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다.
사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.
입력
첫째 줄에 n, k가 주어진다. (1 ≤ n ≤ 100, 1 ≤ k ≤ 10,000) 다음 n개의 줄에는 각각의 동전의 가치가 주어진다. 동전의 가치는 100,000보다 작거나 같은 자연수이다. 가치가 같은 동전이 여러 번 주어질 수도 있다.
출력
첫째 줄에 사용한 동전의 최소 개수를 출력한다. 불가능한 경우에는 -1을 출력한다.
코드
#include <algorithm>
#include <cstring>
#include <iostream>
#include <map>
#include <set>
#include <stack>
#include <queue>
#include <vector>
using namespace std;
const int INF = 999999;
int n, k;
vector<int> money;
int cache[101][10001];
int memoBot[10000];
int dp(int pick, int price){
if(price == 0){
return 0;
}
if(price < 0){
return INF;
}
int& ret= cache[pick][price];
if(ret != -1){
return ret;
}
ret = INF;
for(int i=pick; i<n; ++i){
ret = min(ret, dp(i, price-money[i]) + 1);
}
return ret;
}
int bottomUp(){
for(int i=1; i<=k; ++i){
memoBot[i] = INF;
for(int j = 0; j<n; ++j){
if(i-money[j] >= 0){
memoBot[i] = min(memoBot[i], memoBot[i-money[j]] + 1);
}
}
}
}
int main(void){
memset(cache, -1, sizeof(cache));
int minn = 9999;
cin >> n >> k;
for(int i=0; i<n; ++i){
int a;
cin >> a;
money.push_back(a);
}
int ans = dp(0, k);
if(ans == INF){
cout << -1;
}
else{
cout << ans;
}
}
오랜만에 dp 문제를 풀어봤다.
bottom-up 방식과 top-down 방식을 둘다 사용해봤는데
먼저 bottom-up방식은 재귀를 활용한 방법으로써 위에선 cache배열에 인자로 뽑을 동전의 종류(pick)와 남은 가격(price)를 인자로 줬다.
그래서 만약 INF를 리턴하면 한번도 price가 0이 된 적이 없으므로 -1을 출력한다.
top-down 방식은 dp배열 (여기선 memoBot)을 만들어서 0부터 15까지 쭉 나열한다음 한번 값을 써본다.
그리고 값들에서 규칙을 찾아 점화식을 만들어서 코드로 작성해주는 방식으로 만들어 주면 된다.
아직 top-down 방식에 익숙치가 않아 좀 더 공부가 필요할 듯 하다.
728x90
반응형
'PS > DP' 카테고리의 다른 글
[14501] 퇴사 (0) | 2023.07.03 |
---|---|
[2133] 타일 채우기 (0) | 2023.06.27 |
[11054] 가장 긴 바이토닉 부분 수열 (0) | 2023.04.29 |
[11053] 가장 긴 증가하는 부분 수열 (0) | 2023.04.16 |
[2156] 포도주 시식 (0) | 2023.04.14 |