백준 23559 (C++) 밥

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

23559번: 밥

 

틀린 코드

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
int n, x;
vector<pair<int, int> > v;
bool cmp(pair<int, int> p1, pair<int, int> p2) {
    double a = (double)(p1.first) / (double)(p1.second);
    double b = (double)(p2.first) / (double)(p2.second);
    if (a == b) {
        return p1.first > p2.first;
    }
    return a > b;
}
int main(void) {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> x;
    for (int i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;
        v.push_back({a,b});
    }
    sort(v.begin(), v.end(), cmp);
    for (int i = 0; i < n; i++) {
        cout << v[i].first << " " << v[i].second << '\n';
    }
    int taste = 0;
    for (int i = 0; i < n; i++) {
        if (x <= 0) {
            break;
        }
        if (x >= 5000) {
            if (v[i].first < v[i].second) {
                x -= 1000;
                taste += v[i].second;
                continue;
            }
            x -= 5000;
            taste += v[i].first;
        }
        else {
            x -= 1000;
            taste += v[i].second;
        }
    }
    cout << taste;
    return 0;
}

p1과 p2의 a/b 비율 차이로 정렬해야할 거라고 생각했다.

자꾸 틀려서 a-b의 절댓값 내림차순으로 수정했다. (그래도 틀렸지만)

그리디를 풀 때 수학적인 확신에 기반해서 식 세우는 연습이 필요하다 느꼈다.

 

모든 경우 b를 선택함을 가정하고 해결하는 풀이는 끝내 떠올리지 못하고, 구글링을 통해 해결했다.

 

참고한 글:

https://boomrabbit.tistory.com/200?category=755431 

[ boj : 23559 ] 밥

 

AC

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
int n, x;
int taste = 0;
vector<pair<int, int> > v;
bool cmp(pair<int, int> p1, pair<int, int> p2) {
    int a = abs(p1.first - p1.second);
    int b = abs(p2.first - p2.second);
    if (a == b) {
        return p1.second > p2.second;
    }
    return a > b;
}
int main(void) {
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    cin >> n >> x;
    for (int i = 0; i < n; i++) {
        int a, b;
        cin >> a >> b;
        v.push_back({a,b});
        taste += b;
    }
    sort(v.begin(), v.end(), cmp);
    
    int money = n*1000;
    x -= money;
    for (int i = 0; i < n; i++) {
        if (x <= 0) {
            break;
        }
        if (v[i].first > v[i].second && x >= 4000) {
            taste += v[i].first - v[i].second;
            x -= 4000;
        }
    }
    cout << taste;
    return 0;
}