[백준] #23559 밥

문제

그리디 문제였다. x가 5000보다 클때, 작을 때, 같을 때로 나눠서 풀었는데 이유를 알 수 없게 틀렸다.. 반례를 찾아보려했지만 찾지 못해서 새로운 아이디어로 풀었다. 우선 1000원짜리를 먹는다고생각하고 1000원짜리 맛을 다 더한다음에 5000원짜리가 주는 이득이 더 크고 돈을 낼 여유가 된다면 5000원짜리 맛을 더해주고 1000원자리 맛을 빼주는 코드이다. (맛 이외에 돈도 계산해줘야함)

#include<iostream>
#include<vector>
#include<algorithm>
#include<functional>

using namespace std;

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    int i=0;
  int A[100001],B[100001];
    int n,x,ans=0;
    vector<pair<int,int>> c;
    cin>>n>>x;
    
    for(int i=0;i<n;i++){
        cin>>A[i]>>B[i];
        c.push_back(make_pair(A[i]-B[i],i));
        ans+=B[i];
        x-=1000;
    }
    //cout<<ans<<"\n";
    sort(c.begin(),c.end(),greater<>());

    for(int i=0;i<n;i++){
        //cout<<x<<" "<<c[i].first<<"\n";
        if(c[i].first>0){
            if(x>=4000){
                x-=4000;
                ans-=B[c[i].second];
                ans+=A[c[i].second];
               // cout<<ans<<"\n";
            }
        }
        
    }
   
    cout<<ans;
    return 0; 
}