[BOJ 15590] Rental Service

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

15590번: Rental Service

 

- 문제 요약

 

소의 마릿수 N, 농장 근처 상점의 개수 M, 이웃 농부의 수 R이 첫 번째 줄에 주어진다.

두 번째 줄부터는 1~N번째 소가 하루 동안 생산할 수 있는 우유의 양이 주어진다.

그리고 M개의 상점이 구매하려는 qi(우유의 양), pi(가격)가 M줄 입력된다.

마지막으로 이웃 농부가 소를 임대했을 때 하루 임대료가 R개 주어진다.

농부 존이 하루 동안 벌 수 있는 최대 금액을 출력하시오.

 

 

- 알고리즘 정리

 

우선 우유 생산량에 따라 내림차순으로 정렬해줍니다.

그리고 정렬해준 순서대로 우유를 짜서 가장 비싸게 사는 사람한테 판매해줍니다.

여기서 그냥 쭉 우유를 팔기만 하면 최대 금액이 나오지 않으므로 임대를 해주는 경우도 생각해야 합니다.

 

이때 누적합을 사용해주면 됩니다.

대여 희망자에 대한 누적합을 구해주면서 최종 출력 값인 result가 더 커지는가 아닌가를 판별해줍니다.

만약 같거나 작다면 break를 걸어주고 더 커진다면 계속 진행을 해주면 최적의 값이 구해질 겁니다.

 

 

- 코드 작성

 

#include<cstdio>
#include<iostream>
#include<algorithm>
using namespace std;

typedef long long ll;
ll n,m,r,arr[100001],brr[100001],sum[100001];
pair<ll,ll>p[100001];

bool f(ll a,ll b){
	return a>b;
}

bool ff(pair<ll,ll> a,pair<ll,ll> b){
	return a.second>b.second;
}

int main(){
	cin>>n>>m>>r;
	for(int i=1;i<=n;i++){
		cin>>arr[i];
	}
	for(int i=1;i<=m;i++){
		cin>>p[i].first>>p[i].second;
	}
	for(int i=1;i<=r;i++){
		cin>>brr[i];
	}
	sort(arr+1,arr+1+n,f);
	sort(p+1,p+1+m,ff);
	sort(brr+1,brr+1+r,f);
	for(int i=1;i<=r;i++){
		sum[i]=sum[i-1]+brr[i];
	}
	ll mn=min(r,n),w=0,idx=1;
	ll result=sum[mn];
	for(int i=1;i<=n;i++){
		ll mx=arr[i];
		while(idx<=m&&p[idx].first<=mx){
			w+=p[idx].first*p[idx].second;
			mx-=p[idx++].first;
		}
		w+=mx*p[idx].second;
		p[idx].first-=mx;
		ll aaa=min(r,n-i);
		ll num=sum[aaa]+w;
		if(num>result){
			result=num;
		}
		else{
			break;
		}
	}
	cout<<result;
}

 

마구잡이로 구글링도 하고 그냥 생각나는 대로 짠 코드라 좀 많이 지저분해 보이는 것 같습니다.

변수 명도 이상하게 해 놔서... 나중에 코드를 다시 본다면 무슨 코든지 생각나지 않을 것 같습니다.

나중에 깔끔하게 고쳐놔야겠네요.

 

코드 제출 결과