boj 23559 밥

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

 

A 메뉴를 선택할 수 있다면 선택하는 것이 좋습니다.

하지만 보유중인 금액은 한계가 있으므로 최적의 선택을 하기 위해 A, B 메뉴 맛의 차이가 큰 것을 선택하는 것이 좋습니다.

그래서 A - B를 기준으로 내림차순 정렬해줍니다.

 

그다음 0원으로 시작하여 A를 선택하게 되면 나중에 금액이 부족해질 수 있습니다.

따라서 시작 금액을 모든 메뉴를 B로 선택하는 N * 1000으로 세팅할 수 있습니다.

그렇게 한다면 A 메뉴를 선택했을 때 4000원만 추가해주면 되고, 금액이 부족해지면 추가금액 없이 B를 선택해줄 수 있습니다.

 

 

#include <iostream>
#include <algorithm>
#define MAX 100001
using namespace std;
typedef pair<int, int> pii;
 
pii list[MAX];
int N, X;
 
bool cmp(pii a, pii b) {
    return a.first - a.second > b.first - b.second;
}
 
void func() {
    sort(list, list + N, cmp);
 
    int ret = 0;
    int cost = N * 1000;
    for (int i = 0; i < N; i++) {
        if (cost + 4000 <= X && list[i].first > list[i].second) {
            cost += 4000;
            ret += list[i].first;
        }
        else ret += list[i].second;
    }
    cout << ret << '\n';
}
 
void input() {
    cin >> N >> X;
    for (int i = 0; i < N; i++) {
        cin >> list[i].first >> list[i].second;
    }
}
 
int main() {
    cin.tie(NULL); cout.tie(NULL);
    ios::sync_with_stdio(false);
 
    input();
    func();
 
    return 0;
}