[백준 4781][C++] 사탕 가게

문제 링크

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

4781번: 사탕 가게

 

---

◆문제 해결 및 설명◆

문제 해설 : 사탕 가게에 있는 모든 사탕의 가격과 칼로리가 주어졌을 때, 어떻게 하면 칼로리의 합이 가장 크게 되는지를 구하는 프로그램을 작성하시오.

 

보자마자 DP를 사용한 배낭문제를 떠올렸고, 이와 다른점은 중복된 캔디를 넣을 수 있음을 파악하고 코드를 작성하였다.

가격이 소수형이라서 이를 정수로 처리하기 위해 100을 곱해주었다.

부동소수점 방식의 문제로 소수의 오차가 발생하는 것은 0.005를 더해주어 방지하였다.(제공되는 가격은 소수 둘째자리까지여서 3자릿수를 더해주었다.)

(오차의 예는 10.03을 저장하고 출력하면 10.02가 되는 것을 볼 수 있다.)

        cin >> Case >> Money;
        if (Case == 0 && Money == 0)
        {
            break;
        }
        Money += 0.005;
        int money = Money * 100;

 

하나의 열(vec)을 만들고 vec[i] = max(kcal + vec[i - price], vec[i]); 계산식을 통해 가장 최고의 칼로리가 되는 값을 DP로 구현하였다.

 

처음에는 max_element를 사용해서 최적을 찾았는데, DP를 사용했기 때문에 vec[money]에 최적의 값을 가지고 있음을 뒤늦게 알게되어 속도 향상을 위해 수정하였다.

        // cout << *max_element(vec.begin(), vec.end()) << endl;
        cout << vec[money] << endl;

 

◆코드 전문◆

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int Case;
    double Money;

    while (1)
    {
        cin >> Case >> Money;
        if (Case == 0 && Money == 0)
        {
            break;
        }
        Money += 0.005;
        int money = Money * 100;

        vector<pair<int, int>> items;
        for (int i = 0; i < Case; i++)
        {
            int kcal;
            double price;
            cin >> kcal >> price;
            price += 0.005;
            price *= 100;
            items.push_back({kcal, price});
        }

        vector<int> vec(money + 100, 0);
        for (int k = 0; k < items.size(); k++)
        {
            int kcal, price;
            tie(kcal, price) = items[k];

            for (int i = price; i <= money; i++)
            {
                vec[i] = max(kcal + vec[i - price], vec[i]);
            }
        }
        
        // cout << *max_element(vec.begin(), vec.end()) << endl;
        cout << vec[money] << endl;
    }
}