[PS] 백준 23559번 밥

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

모든 경우의 수를 하려면 O(2 ^ n)이므로 브루트 포스로는 풀 수 없다.
다만 이것을 알고리즘 문제가 아니라 자기자신이 밥먹을 계획을 세운다고 생각한다면 간단하게 풀이가 나온다!

밥을 굶는 날이 있으면 안되기 때문에 모든 날에 뭐라도 먹는다. -> 모든 날에 1000원어치 식사를 한다.
굶는 것은 면했으니 남은 돈으로 '맛'을 최대화해야 한다.
따라서, 임의의 날짜에 1000원어치 식사를 5000원 식사로 바꿔야 하는데, 바꿨을 때 '맛'이 최대로 증가하는 날부터 바꾸어야 하겠다. 당연히 맛이 증가하지 않거나 더 감소하는 날은 바꾸지 말아야하겠다.
그래서 날짜별 5000원 어치 맛 - 1000원 어치 맛 이 차이중 0 초과인 것을 내림차순 정렬하고, 예산 내에서 5000원 어치 식사로 바꿔가면 되겠다.

#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <algorithm>

using namespace std;

int n, x;
int a[100000];
int b[100000];

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	cin >> n >> x;

	for (int i = 0; i < n; i++) {
		cin >> a[i] >> b[i];
	}

	int cost = 1000 * n;
	int taste = 0;
	for (int i = 0; i < n; i++) {
		taste += b[i];
	}

	priority_queue<int> pq;
	for (int i = 0; i < n; i++) {
		int diff = a[i] - b[i];
		if (diff <= 0) {
			continue;
		}

		pq.push(diff);
	}

	while (!pq.empty()) {
		if (cost + 4000 > x) {
			break;
		}
		taste += pq.top();
		pq.pop();
		cost += 4000;
	}
	
	cout << taste << "\n";

	return 0;
}