[백준 23599 - C++] 밥

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

23559번: 밥

 

programmers 만 풀다가 오랜만에 백준 문제를 풀었다! 

문제를 읽어보면 딱 봐도 그리디이다. 처음에는 맛 / 가격 을 해서 효율을 따지려 했는데 문제에서 주어진 첫 예제부터 이게 아니라는 것을 알았다. 예제 입력 1 에서 40 / 5000 < 10 / 1000 인데 첫 날 5000 짜리 메뉴를 고르는 게 정답이다. 다음 생각한 것은 아주 그리디하게 

1. 일단 전부 1000원 짜리 메뉴를 고른다.

2. 5000 짜리 메뉴와 1000원 짜리 메뉴의 맛의 차가 큰 날짜가 먼저오게 날짜를 정렬한다.

3. 날짜를 정렬한 순서대로 탐색하면서 돈이 허락하는 한에서 5000원 짜리 메뉴로 바꾼다.

이렇게 하니 되더라. 그리디는 역시 일단 우겨보는게 정답이다. 

 

전체 코드이다.

#include <iostream>
#include <cstring>
#include <string.h>
#include <string>
#include <cmath>
#include <vector>
#include <numbers>
#include <math.h>
#include <algorithm>
#include <list>
#include <stack>
#include <queue>
#include <deque>
#include <tuple>
#include <utility>
#include <typeinfo>
#include <iomanip>
#include <set>
#include <map>

using namespace std;

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

vector<pair<int, int>> lunch;
int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    int n, x;
    cin >> n >> x;

    int mat = 0;
    int a, b;
    for (int i = 0; i < n; i++) {
        cin >> a >> b;
        mat += b;
        lunch.push_back({ a,b });
    }

    sort(lunch.begin(), lunch.end(), cmp);

    int money = 1000 * lunch.size();
    for (int i = 0; i < lunch.size(); i++) {
        
        if (lunch[i].first > lunch[i].second) {
            money += 4000;
            if (money > x) break;
            mat = mat - lunch[i].second + lunch[i].first;
        }
    }
    cout << mat;
}