ps

동전1, 동전2, 사탕가게

유사한 문제라서 모아서 풀이해보기

동전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