문제

입력

입출력 예시

코드

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

int N, K;
vector<pair<int, int>> fruits;

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

int main() {
	cin >> N >> K;
	fruits = vector<pair<int, int>> (N, {0, 0});
	
	for(int i = 0; i < N; i++) {
		cin >> fruits[i].first >> fruits[i].second;
	}
	sort(fruits.begin(), fruits.end(), cmp);
	
	int i = 0;
	long long answer = 0;
	while(K >= 0 && i < N) {
		if(K >= fruits[i].first) {
			answer += fruits[i].second;
			K -= fruits[i].first;
			++i;
		}
		else{
			int piece = fruits[i].second / fruits[i].first;
			answer += piece * K;
			break;
		}
	}
	cout << answer;
	return 0;
}

포만감이 최대인 경우를 구해야하므로 greedy 알고리즘을 이용하여 풀 수 있다.
조각 당 포만감이 큰 순으로 정렬하고, 과일을 통째로 살 수 있는 경우( K >= fruits[i].first )와 그렇지 않는 경우(살 수 있는 만큼의 조각을 구매)를 구분한다.
과일을 통째로 사지 못하는 경우는 마지막 한 과일밖에 없으므로 이 경우 포만감을 더해주고 break 를 통해 while 문을 끝내면 된다.