백준 #14908 구두 수선공

이 문제도 그리디를 이용한 문제였는데, 풀이 방식이 저번에 풀었던 

https://miffu-bh.tistory.com/31

백준 #23559 밥

거의 유사하고, 최적의 해를 찾기 위한 방식만 약간 다른 문제였다. 

수선공이 보상금을 가장 적게 지불 하기 위해서 어떤 순서로 작업을 하는것이 가장 좋은지 구해야 한다.

동시에 들어온 작업이기 때문에 하나의 일을 하는 동안 나머지의 모든 작업은 보상금이 매일매일 추가 된다. 그렇기 때문에 

 

작업 일 수 (Ti) 와 보상금의 비율 ( Ti / Si) 이 큰 일 부터 처리하는 것이 가장 보상금을 적게 낼 수 있는 방법일 것이다. 

그렇다면  만약 비율이 같은 경우에는 어떻게 해야할 까? 당연히 처음에는 못떠올린 반례였는데 다행히 예제에서 비율이 1로 같은 작업이 2개가 들어와 고려할 수 있었다. 이 경우 지불해야하는 보상금이 더 큰 작업을 당연히 먼저 작업하면 될것이다! skrr 

 

코드는 다음과 같다. 

이번 문제도 tuple을 이용해 보았다. tuple의 인자로 비율을 넘겨 비율이 더 큰 순으로 정렬하고, 만약 비율이 같은 경우에는 보상금이 더 큰 순으로 정렬되도록 하였다. compare 함수를 제대로 이용하니 이럴 때 참 편리하다.

 

#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>

using namespace std;

bool compare( tuple<double, int, int> a, tuple<double , int, int> b)
{
    if( get<0>(a) == get<0>(b))
        return get<1>(a) > get<1>(b);
    else
        return get<0>(a) < get<0>(b);
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    int n;
    int arr[1002];
    int arr2[1002];
    vector <tuple<double, int, int>> arr3;
    cin>>n;
    for(int i =0; i< n; i++)
    {
        cin>>arr[i] >> arr2[i];
        arr3.push_back(make_tuple((double)arr2[i]/arr[i], i, arr[i]));
    }
    sort(arr3.begin(), arr3.end(), compare);
    
    for(int i =n-1; i>=0;i--)
    {
        cout<< get<1>(arr3[i]) +1<<' ';
    }
    cout<<'\n';
}