[Algorithm] Baekjoon 4781번 : 사탕 가게

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

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_map>
#include <stack>
#include <numeric>
 
using namespace std;
 
int n, t;
float m;
int calories[5001] = { 0 };
int costs[5001] = { 0 };
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    while (1)
    {
        cin >> n >> m;
 
        int maxCost = m * 100 + 0.5;
        if (n == 0 && maxCost == 0) break;
 
        for (int i = 1; i <= n; ++i)
        {
            int a;
            float b;
 
            cin >> a >> b;
 
            calories[i] = a;
            costs[i] = b * 100 + 0.5;
        }
 
        int dp[10001] = { 0 };
 
        for (int i = 1; i <= n; ++i)
        {
            int calorie = calories[i];
            int cost = costs[i];
 
            for (int j = cost; j <= maxCost; ++j)
            {
                dp[j] = max(dp[j], dp[j - cost] + calorie);
            }
        }
 
        printf("%d\n", dp[maxCost]);
    }
}
 
 
 

 

 

각 캔디의 칼로리와 가격이 주어졌을 때, 특정금액으로 얻을 수 있는 최대 칼로리를 구하는 문제이다.

여기서 캔디는 '개수제한 없이' 구매할 수 있다.

 

꽤나 익숙한 유형이다. 동전문제의 여러유형중 한가지와 매우 비슷한 점화식으로 해결할 수 있다.

'무한대로 사용할 수 있는 유한종류개수의 동전이 주어졌을 때.... 어떠어떠한 값을 구하라'

 

라는 문제유형과 비슷하다. 여기서 어떠어떠한값은 뭐 이것저것이 될 수 있다.

특정금액을 만드는 모든 경우의 개수라던가.. 이번문제처럼 특정금액한도내에서 얻을 수 있는 최대칼로리를 구하라고 한다던가..