백준 #23559 밥

ICPC 알고리즘 캠프 초급 반을 듣기 시작했는데, 그동안 풀었던 걸 정리를 해보려고 한다.

 

그리디를 이용해서 푸는 문제인데, 이런 유형의 문제들은 다 비슷비슷하게 정렬하면 풀리는 것 같다!

 

vector<pair<int ,int>>, vector<tuple<int, int, int>> 를 정렬의 인자로 compare 함수를 만드는걸 이 문제를 통해 연습해 볼 수 있었다. 원하는 기준으로 정렬할 수 있단 게 참 좋다!

 

문제는 두 학식 메뉴 중 어떤 메뉴를 골라 먹었을 때 만족도가 가장 클지를 구하는 것이다. 다행히 이제 이런 문제는 보면 그리디로 해결하면 되겠다는 감이 온다! skrr

 

tuple로 벡터를 만들고, 3개의 인자를 더 큰 만족도(larger), 더 작은 만족도(smaller), 그리고 5000원만족도-1000원만족도(tmp2 -tmp1) 로 하였다.

 

우선 만족도가 가장 높은 메뉴들로만 매일 학식을 먹는다 가정하고, 예산의 범위를 초과할 경우  예산 범위안으로 들어올 때까지 만족도의 차이가 가장 적은 것 중, 5000원 짜리의 만족도가 1000원의 만족도보다 더 큰 날을 바꿔준다. 

 이렇게 하면 1000원의 만족도가 5000원의 만족도보다 큰 날도 고려하고, 만족도의 차이가 가장 작은 날부터 1000원짜리 학식을 먹기 시작하기 때문에 그리디하게 문제를 풀었다고 할 수 있다!

 

#include<iostream>
#include<string>
#include <map>
#include<set>
#include<stack>
#include <vector>
#include <functional>
#include <algorithm>
#include<cmath>
#include <cstring>
#include <set>
#include <stdio.h>
//#include <string.h>

using namespace std;

long long int x;

bool compare( const tuple<int, int, int> & a, const tuple <int,int, int> &b)
{
    return get<2>(a) > get<2>(b);
}

vector <tuple<int, int, int>> arr;
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int n;
    int tmp1, tmp2;
    cin>> n >>x;
    long long int sum = 0;
    long long int rate =0;
    
    for(int i =0; i< n; i++)
    {
        cin>> tmp1 >>tmp2;
        rate += max(tmp1, tmp2);                   //일단 만족도 합
        int larger, smaller;
        if(tmp1 > tmp2)
        {
            larger  =tmp1; smaller = tmp2;
        }
        else{
            larger = tmp2; smaller =tmp2;
        }
        arr.push_back(make_tuple(larger, smaller,  tmp2-tmp1));
    }
    
    sort(arr.begin(), arr.end(), compare);
    
    for(int i =0; i< n; i++)
    {
        if( get<2>(arr[i]) > 0)
        {
            sum += 1000;
        }
        else
            sum += 5000;
    }
    //일단 무조건 5000원으로 전부 먹는 경우로 시작해서, 금액에 맞게 조절하고, 1000원이 더 만족도가 클때를 본다   
    int i = 0;

    while(sum > x)
    {
        if(get<2>(arr[i]) <= 0)
        {
            sum -= 4000;
            rate += get<2>(arr[i]);
        }
        i++;
    }
    cout<< rate<<'\n';
}