유사한 문제라서 모아서 풀이해보기
동전2
n가지 종류의 동전이 있다. 이 동전들을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그러면서 동전의 개수가 최소가 되도록 하려고 한다. 각각의 동전은 몇 개라도 사용할 수 있다
여기서 dp[k]는 합이 k가 되는 동전의 최소개수이다.
따라서 합이 0이 되는 동전의 최소개수는 0이기 때문에 dp[0]=0으로 세팅한다.
또한 최소값이 dp에 들어가야하기 때문에 max값으로 세팅해준다.
핵심 로직은
k가 1000원이고 100원의 동전이 있다고 했을 때 1000-100원의 동전 최소개수에 100원 동전 1개를 더하는준 것과 기존 dp[1000]을 비교하여 최소 개수를 구해준다는 것이다.
#include<bits/stdc++.h>
using namespace std;
int n,k;
int dp[100004];
int d;
int main(){
cin >> n >> k;
fill(dp, dp + 100004, 100004);
dp[0] = 0;
for(int i=0; i < n; i++){
cin >> d;
for(int j=d; j<=k; j++){
dp[j] = min(dp[j-d] + 1, dp[j]);
// cout << j << " " << dp[j] << "\n";
}
}
if(dp[k] == 100004){
cout << -1 << "\n";
return 0;
}
cout << dp[k] << "\n";
}
동전1
n가지 종류의 동전이 있다. 각각의 동전이 나타내는 가치는 다르다. 이 동전을 적당히 사용해서, 그 가치의 합이 k원이 되도록 하고 싶다. 그 경우의 수를 구하시오. 각각의 동전은 몇 개라도 사용할 수 있다.
사용한 동전의 구성이 같은데, 순서만 다른 것은 같은 경우이다.
동전 2과 매우 유사한데 경우의 수를 구하는 문제이다. 따라서 dp[k]는 합이 k가 되는 경우의 수이다.
핵심 로직은
k가 1000원이고 100원, 200원, 300원의 동전이 있다고 했을 때 1000원을 만들 수 있는 경우의 수는 900원, 800원, 700원을 만들 수 있는 경우의 수의 합과 같다는 것이다.
#include<bits/stdc++.h>
using namespace std;
int n,k;
int d;
int MAX_N = 10004;
int dp[10004];
int main(){
cin >> n >> k;
fill(dp, dp+MAX_N, 0);
dp[0] = 1;
for(int i=0; i < n ; i++){
cin >> d;
for(int j=d; j <=k; j++){
dp[j] += dp[j-d];
// cout << j << " " << dp[j] << "\n";
}
}
cout << dp[k] << "\n";
}
사탕가게
이 시스템에는 현재 사탕 가게에 있는 사탕의 가격과 칼로리가 모두 등재되어 있다. 각 사탕의 개수는 매우 많기 때문에, 원하는 만큼 사탕을 구매할 수 있다. 또, 사탕은 쪼갤 수 없기 때문에, 일부만 구매할 수 없다.
사탕 가게에 있는 모든 사탕의 가격과 칼로리가 주어졌을 때, 어떻게 하면 칼로리의 합이 가장 크게 되는지를 구하는 프로그램을 작성하시오.
동전 문제들보다 조금 더 어렵다. 변수가 많아졌는데
결국 dp[x](p100s[x])는 x원에 가질 수 있는 최대 칼로리이다.
핵심로직은 m원을 가지고 있고, c칼로리 p원 사탕이 있을 때
m-p원을 가지고 있을 때의 섭취할 수 있는 최대 칼로리에 c 칼로리를 더한 값이 dp[m]이 된다.
#include<bits/stdc++.h>
using namespace std;
int n;
double m;
int c;
double p;
int p100s[10004]; //x원에 가질 수 있는 최대 칼로리
int m100;
int p100;
int main(){
while(true){
fill(p100s, p100s + 10004, 0);
p100s[0] = 0;
cin>> n >> m;
if(n==0 && m == 0){
break;
}
// cout << " n " << "=" << n << " : " << "m : " << m << "\n";
m100 = m * 100.0 + 0.5;
for(int i=0; i <n; i++){
cin >> c >> p;
p100 = p * 100.0 + 0.5;
for(int j=p100; j <= m100; j++){
p100s[j] = max(p100s[j-p100] + c, p100s[j]);
}
}
cout << p100s[m100] << "\n";
}
}
'ps' 카테고리의 다른 글
1로 만들기 2 (0) | 2024.01.24 |
---|---|
비트마스킹은 신기해 (0) | 2022.09.20 |
백준 2583 영역 구하기 (0) | 2022.03.04 |
스택 수열, 백준 1874번 (0) | 2021.01.05 |
동적계획법, dynamic programming 기본 (0) | 2020.12.31 |