효율적으로 소 사기( BOJ 5896 )

문제 : https://www.acmicpc.net/problem/5896

5896번: 효율적으로 소 사기

 

문제 파악하기

농부 존이 구매할 수 있는 소의 최대 개수를 구하는 문제입니다. 소는 일반 가격으로 구매할 수도 있고, 쿠폰을 사용하여 구매할 수도 있으며, 쿠폰을 구매하는 소의 가격은 일반 가격보다 같거나 저렴합니다. 주어지는 소의 개수는 최대 50,000 마리이기 때문에 우리는 최소한 시간 복잡도가 O(NlogN) 이하인 알고리즘이 필요하다는 걸 알 수 있습니다. 그렇다면 어떤 방법이 있을까요?

 

문제 해결하기

가장 먼저 생각할 수 있는 방법은 정렬을 사용하는 방법입니다. 모든 소를 가격이 저렴한 순서대로 정렬한 다음, 순서대로 쿠폰이 있으면 쿠폰을 사용하고, 없으면 일반 가격으로 구매하는 방법입니다. 하지만 이 방법은 특정 경우(참고)에 제대로 작동하지 않게 됩니다.

 

그럼 최대한 많은 소를 구매하기 위해서는 어떻게 탐색해야 할까요? 바로, 쿠폰으로 구매한 소를 계속 바꿔주면 됩니다. 우선 쿠폰 가격으로 소를 정렬한 다음, 모든 소를 탐색해봅니다. 항상 쿠폰으로 구매하는 가격이 저렴하다고 할 수 있기에 쿠폰이 있으면 쿠폰으로 소를 구매합니다. 만약 쿠폰이 떨어졌다면 아래 2가지 경우를 비교합니다.

(1) 현재 소를 일반 가격으로 구매하는 경우

(2) 현재 소를 쿠폰으로 구매하고, 쿠폰으로 구매한 소 중에서 하나를 일반 가격으로 구매하는 경우

 

만약, 2가지 경우 모두 불가능하다면 해당 소는 구매하지 않습니다. 만약 (1)번과 (2)번 모두 가능하다면 우리는 현재 소를 구매했을 때, 남은 돈이 가장 많은 경우를 선택하면 됩니다. 여기서 한 가지 의문이 들 수 있습니다. 그럼 쿠폰으로 구매한 소 중에서 어떤 소를 선택할까? 바로, 일반 가격이 가장 저렴한 소를 선택하면 됩니다. 일반 가격이 가장 저렴한 소를 선택해야 다른 소를 쿠폰으로 구매할 때, 남는 돈이 가장 많아질 수 있기 때문입니다. 여기까지 구현한다면 문제를 해결 할 수 있습니다.

 

소스코드

#include <stdio.h>
#include <queue>
#include <vector>
#include <utility>
#include <algorithm>
#define lint long long int
#define PAIR pair<lint, lint>
using namespace std;
 
lint N, K, M, p, c;
vector< PAIR > inp;
 
int cnt;
struct compare {
    bool operator()(PAIR a, PAIR b) { return a.first > b.first; }
};
priority_queue< PAIR, vector< PAIR >, compare > pq;
 
bool cmp(PAIR a, PAIR b) {
    if(a.second == b.second) return a.first < b.first;
    else return a.second < b.second;
}
 
int main() {
    scanf("%lld %lld %lld", &N, &K, &M);
    for(int i= 0;i<N;i++) {
        scanf("%lld %lld", &p, &c);
        inp.push_back({p, c});
    }
 
    sort(inp.begin(), inp.end(), cmp);
 
    for(int i=0;i<N;i++) {
        // 쿠폰이 있는 경우, 바로 사용하기
        if(K>0) {
            if(M < inp[i].second) break;
 
            M -= inp[i].second;
            pq.push(inp[i]);
            
            K--;
            cnt++;
        }
 
        // 쿠폰을 다 사용한 경우
        else {
            lint a, b;
            PAIR top = pq.top();
 
 
            // 쿠폰을 사용하지 않아도 되는 경우
            a = M - inp[i].first;
 
            // 쿠폰을 사용해야 하는 경우
            b = (M+top.second) - (top.first+inp[i].second);
 
 
            if(a<0 and b<0) continue;
            else cnt++;
 
            if(a >= b) M = a;
            else {
                M = b;
 
                pq.pop();
                pq.push(inp[i]);
            }
        }
    }
 
    printf("%d", cnt);
}
 
/*
4 2 15
10 1
3 2
6 4
9 5
ans: 4
 
2 1 7
10 4
2 1
ans: 2
 
3 1 3
10000 1
10000 1
2 2
ans: 2
*/

후기

정렬 및 우선순위큐를 사용하는 문제입니다. 쿠폰을 사용하는 소를 계속 바꿔주어야 한다는 점을 간과해서 문제가 쉽게 풀리지 않았던 기억이 있습니다. 우선순위 큐에 대해 배웠다면 심화 문제로 풀기 좋은 문제라고 생각합니다.