백준 2258 - 정육점

문제 설명

은혜는 정육점에서 고기를 사려고 한다. 보통 정육점에서는 자신이 원하는 양을 이야기하면 그 양만큼의 고기를 팔지만, 은혜가 방문한 정육점에서는 세일 행사를 하고 있었기 때문에 N 덩어리의 고기를 이미 잘라놓고 판매하고 있었다.

각각의 덩어리들은 이미 정해져 있는 무게와 가격이 있는데, 어떤 덩어리를 샀을 때에는 그 덩어리보다 싼 고기들은 얼마든지 덤으로 얻을 수 있다(추가 비용의 지불 없이). 또한 각각의 고기들은 부위가 다를 수 있기 때문에 비용과 무게와의 관계가 서로 비례하는 관계가 아닐 수도 있다. 은혜는 이러한 점을 고려하지 않고, 어느 부위든지 자신이 원하는 양만 구매하면 되는 것으로 가정한다. 또한 만약 가격이 더 싸다면 은혜가 필요한 양보다 더 많은 고기를 살 수도 있다.

각 덩어리에 대한 정보가 주어졌을 때, 은혜가 원하는 양의 고기를 구매하기 위해 필요한 최소 비용을 계산하는 프로그램을 작성하시오.

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, N개의 고기에 대한 정보가 주어진다.

무게(w)와 가격(v)이 주어졌을 때 M이상의 고기를 사려면 최소 얼마를 써야 하는지 구해야 한다.

이때, 고기를 하나 산다고 했을 때 그 고기보다 싼 고기는 공짜로 얻을 수 있다.

예를 들어, {1, 2}, {2, 4}, {3, 6}의 고기가 있었다고 가정해 보자. (무게, 가격)

이때, 두 번째 고기(가격: 4)를 산다고 하면 첫 번째 고기는 더 싸기 때문에 공짜로 얻을 수 있다.

 

해당 문제는 정렬을 통해 간단하게 해결할 수 있다.

고기를 싼 가격에 M이상의 무게를 구하기 위해서는 최대한 무거운 고기를 싸게 사야 한다.

또한, 해당 고기보다 낮은 가격의 고기는 공짜로 얻을 수 있다는 점을 고려해야 한다.

즉, 고기를 가격순으로 정렬한다면 자신보다 앞에 나오는 고기는 모두 공짜라는 얘기가 된다.

단, 가격이 같은 고기는 더 무거운 고기가 앞에 나오는 것이 유리하다. 

가격이 같은 고기는 공짜가 아니기 때문에 최대한 적게 사야하기 때문이다.

정리하자면, 고기를 가격순으로 정렬하되 가격이 같다면 무거운 순으로 정렬하면 된다.

bool cmp(const pair<long long, long long>& a, const pair<long long, long long>& b)
{
    if (a.second == b.second) return a.first > b.first;
    return a.second < b.second;
}

 

이후, 정렬된 고기 배열의 앞에서부터 무게를 더해나간다.

만약, 무게의 합이 M이상이라면 정답을 갱신한다.

이때, 정답은 가격이 될 것이다.

하지만, 앞서 말했듯이 유의할 점은 가격이 같은 고기들을 어떻게 처리할 것인지이다.

가격이 같은 고기는 뒤에 나오는 고기를 산다고 하더라도 공짜가 되지 않는다.

따라서, 가격이 이전 고기와 가격이 같은 고기는 정답에 가격을 더해주고 더 비싼 고기는 비싼 고기 하나만 사더라도 앞에 나오는 모든 고기들이 공짜이기 때문에 갱신한다.

for (int i = 1; i < N; i++)
{
    sum += meats[i].first;
    

    if (meats[i].second == meats[i - 1].second)
    {
        //가격이 같은 고기
        temp += meats[i].second;
    }
    else
    {
        //비싼 고기
        temp = meats[i].second;
    }

    if (sum >= M)
    {
        ans = min(ans, temp);
    }
}

자신의 앞에 나오는 고기와 비교가 필요하기 때문에 0번 인덱스의 고기는 예외가 발생한다.

코드를 간결하게 쓰기 위해 0번 인덱스는 따로 처리해 주자.

long long sum = meats[0].first;
long long temp = meats[0].second;
long long ans = LLONG_MAX;

if (sum >= M)
{
    cout << temp;
    return 0;
}

 

또한, 모든 고기를 사더라도 M을 넘지 못하는 경우가 존재한다.

이를 위해, 마지막에 확인하는 과정을 추가한다.

if (sum < M) cout << -1;
else cout << ans;

---

 

 

 

 

 

전체 코드

#include <stdio.h>
#include <cstring>
#include <string>
#include <vector>
#include <algorithm>
#include <iostream>
#include <sstream>
#include <cmath>
#include <climits>
#include <queue>
#include <map>
#include <unordered_map>
#include <unordered_set>
#include <set>
#include <list>
#include <bitset>

using namespace std;

long long N, M;

bool cmp(const pair<long long, long long>& a, const pair<long long, long long>& b)
{
    if (a.second == b.second) return a.first > b.first;
    return a.second < b.second;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cout.precision(4);

    cin >> N >> M;

    vector<pair<long long, long long>> meats;
    for (int i = 0; i < N; i++)
    {
        int w, v;
        cin >> w >> v;
        meats.push_back({ w, v });
    }

    sort(meats.begin(), meats.end(), cmp);

    long long sum = meats[0].first;
    long long temp = meats[0].second;
    long long ans = LLONG_MAX;

    if (sum >= M)
    {
        cout << temp;
        return 0;
    }

    for (int i = 1; i < N; i++)
    {
        sum += meats[i].first;
        if (meats[i].second == meats[i - 1].second)
        {
            temp += meats[i].second;
        }
        else
        {
            temp = meats[i].second;
        }

        if (sum >= M)
        {
            ans = min(ans, temp);
        }
    }

    if (sum < M) cout << -1;
    else cout << ans;

    return 0;
}

---