[BOJ 5896] 효율적으로 소 사기

 

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

5896번: 효율적으로 소 사기

 

- 문제 요약

 

농부 존은 새 소들이 필요하다! 그래서 농부 존은 소 시장에 가서 새 소들을 사려고 한다.

농부 존은 돈이 많이 없기 때문에 소들을 최대한 효율적으로 사야 한다. 그래서 농부 존은 M원과 K개의 소 쿠폰을 가지고 소 시장에 나온 N마리의 소들을 최대한 많이 사려고 한다.

소 쿠폰은 소 한 마리당 한 번만 쓸 수 있고, 쓰고 나면 사라진다. i번째 소는 Pi원이고, 쿠폰을 썼을 때는 Ci원이 될 때, 농부 존이 최대로 살 수 있는 소의 마릿수를 출력하라.

 

 

- 알고리즘 정리

 

첫 번째로 생각해 낸 아이디어는 비용이 적은 순(Pi 기준 오름차순)으로 정렬한 후 쿠폰을 사용하며 소를 구매하는 방법으로 코드를 짜려했는데, 이렇게 하면 Pi와 Ci의 격차가 큰 소를 놓치는 경우가 생기게 됩니다. ( = 반례가 생긴다 )

그렇기에 소를 정렬할 때, Ci 기준으로 정렬 후 쿠폰을 사용하는 경우와 사용하지 않는 경우를 나눠서 처리해줍니다. 쿠폰이 남아있을 때 쿠폰을 사용하는 경우와 사용하지 않는 경우를 비교해서 돈이 많이 남는 경우를 선택하면 됩니다.

 

 

- 코드 작성

 

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
ll n,k,m,a,b,result;
vector<pair<ll,ll> >v;
struct compare{
	bool operator()(pair<ll,ll>a,pair<ll,ll>b){
		return a.first>b.first;
	}
};
priority_queue<pair<ll,ll>,vector<pair<ll,ll> >,compare>pq;

bool cmp(pair<ll,ll>a, pair<ll,ll>b){
	if(a.second==b.second){
		return a.first<b.first;
	}
	else{
		return a.second<b.second;
	}
}

int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);
	cin>>n>>k>>m;
	for(int i=0;i<n;i++){
		cin>>a>>b;
		v.push_back({a,b});
	}
	sort(v.begin(),v.end(),cmp);
	for(int i=0;i<n;i++){
		if(k>0){ // 쿠폰있음 
			if(m<v[i].second){
				break;
			} 
			m-=v[i].second;
			pq.push(v[i]);
			k--;
			result++;
		}
		else{ // 쿠폰없음 
			ll aa,bb;
			pair<ll,ll>t=pq.top();
			aa=m-v[i].first;
			bb=(m+t.second)-(t.first+v[i].second);
			if(aa<0 and bb<0){
				continue;
			}
			else{
				result++;
			}
			if(aa>=bb){
				m=aa;
			}
			else{
				m=bb;
				pq.pop();
				pq.push(v[i]);
			}
		} 
	}
	cout<<result;
}

코드 제출 결과

아이디어 떠올리는게 힘들었던 문제...

코드 구현은 간단한데 쿠폰을 사용하는 경우의 수를 나누고 그걸 우선순위 큐에 접목시킬 아이디어를 떠올려야 하니...

플3 정도의 문제는 맞는 것 같네요.