[백준 14908번] 구두 수선공 (C++)

문제링크 : https://www.acmicpc.net/problem/14908

14908번: 구두 수선공

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

pair<float, int> arr[10001]; //비용, 순서

bool cmp(pair<float, int>& a, pair<float, int>& b)
{
    if(a.first == b.first) return a.second < b.second;
    else return a.first > b.first;
}

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    int N;
    cin >> N;

    for(int i=0; i<N; i++)
    {
        float T, S;
        cin >> T >> S;
        arr[i] = {S/T, i}; //시간대비 비용과 순서 입력
    }

    sort(arr, arr+N,cmp); //시간대비 비용 내림차순으로 정렬 (같으면 순서 인덱스가 큰 것부터)

    for(int i=0; i<N; i++) //시간대비 비용이 제일 큰 것부터 출력 (제일 리스크 비용이 큰 것부터)
    {
        cout << arr[i].second + 1<< " ";
    }
    
    return 0;
}

최저보상금을 지불하기 위해서는 시간대비 비용을 계산하여 비용이 큰 것부터 출력해야 한다고 생각했다.

따라서 시간대비 비용을 계산하고 해당 비용과 현재 순서를 같이 pair 배열에 저장하였다.

 

문제에서 여러가지 해답이 나오는 경우 오름차순 정렬에 의해 가장 첫 번째 해답이 나오도록 명시되어있는데

해당 문제의 예제를 보면

4
3 4
1 1000
2 2
5 5

시간대비 비용이 1.33333 / 1000 / 1 / 1 인 것을 볼 수 있다.

여기서 비용이 1, 1로 같은 것을 볼 수 있는데, 이런 경우에는 가장 첫 번째 해답이 나오도록 같이 넣었던 순서가 가장 빠른 것부터 나오도록 커스텀 정렬을 하였다.

 

따라서 <1.33333, 0>, <1000, 1>,  <1, 2>, <1, 3> 인 것을 알 수 있고, 비용이 가장 비싼 1번째 0번째 순서로 출력했다가

이후 비용이 같은 2와 3중 순서가 빠른 2부터 출력하는 것을 알 수 있다.

여기서 i=0부터 시작하기에 0부터지만, 문제에서는 1부터이므로 순서를 출력할때 1을 더해주었다.