[BOJ][C++] 백준 14908번: 구두 수선공 (Gold I)

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

 

문제

지금 구두 수선공에게는 손님으로부터 주문 받고 제작해야 할 작업이 N개 쌓여있다. 구두 수선공은 하루에 한 작업만 수행할 수 있고, i번째 작업을 완료하는 데 Ti일이 걸린다. 이때 Ti는 정수이고 1 ≤ Ti≤ 1000이다.
i번째 작업을 시작하기 전에 하루가 지연될 때마다 구두 수선공은 보상금 Si센트를 지불해야 한다. 이때 Si는 정수이고 1 ≤ Si≤ 10000이다. 구두 수선공을 돕기 위해 최저 보상금을 지불하는 작업 순서를 정해야 한다.
하루에 2개 이상의 작업을 동시에 수행할 수 없다. 작업 i를 수행하고 있는 경우, 작업 i를 마칠 때 까지 작업 i 외의 다른 작업을 수행할 수 없다.

입력

1 ≤ N ≤ 1000 범위의 정수 N이 첫 번째 줄에 주어진다. 다음 N개 줄에 걸쳐서 첫 번째 열에는 T1… TN이 입력되며, 두 번째 열에는 S1… SN이 주어진다.

출력

최소 보상금을 지불하는 작업 순서를 출력해야 한다. 모든 작업은 입력에서의 번호(1~N)로 표시해야 한다. 모든 정수는 한 줄로 표시해야 하며, 각 작업은 공백 문자로 구분한다. 여러 가지 해답이 나올 수 있다면 오름차순 정렬에 의해 가장 첫 번째 해답을 출력한다.

 

풀이

s/t, 즉 마감하는 날짜 당 보상금을 기준으로 그 비가 큰 일 부터 먼저 처리해야한다

필자는 tuple을 이용해 인덱스와 s와 t를 다 넣긴 했는데, 그냥 pair로 해서 인덱스와 s/t를 바로 넣는게 훨씬 나을 것 같다.

 

비율이 같다면 인덱스가 더 작은걸 먼저 배치한다

(문제 마지막 줄에 있음.

이거 처리 안하면 7퍼센트에서 틀렸습니다 뜸)

// 풀이 : https://whkakrkr.tistory.com

#include <iostream>
#include <vector>
#include <tuple>
#include <algorithm>

using namespace std;

typedef tuple<int, int, int> ci;

bool cmp(ci a, ci b) {
    float a_ratio = (float) get<2>(a) / get<1>(a);
    float b_ratio = (float) get<2>(b) / get<1>(b);
    
    if(a_ratio == b_ratio) {
        return get<0>(a) < get<0>(b);
    }
    return a_ratio > b_ratio;
}

int main() {
    ios_base::sync_with_stdio(false);
	cout.tie(NULL);
	cin.tie(NULL);
	
	// input
	int n;
	float t,s;
	cin >> n;
	vector<ci>v;
	for(int i=1; i<=n; i++) {
	    cin >> t >> s;
	    v.push_back(make_tuple(i, t, s));
	}
	
	// solution
	sort(v.begin(), v.end(), cmp);
	
	// output
	for(int i=0; i<n; i++) {
	    cout << get<0>(v[i]) << " ";
	}
	
    return 0;
}