구두 수선공 C++ - 백준 14908

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

(이 영상을 참고했습니다)

이 문제는 그리디 알고리즘의 증명법 영상을 찾아보다가 알게되어 풀게 되었다.

그리디 알고리즘의 증명은 일반적으로는 어렵다.

그중 여러가지 증명방식이 있는데 이번에 본 증명방식은 Exchange Argument이다.

최적해를 가정한 후 두 원소 중 순서를 정할때 어떤 방식을 정해야 최적해가 되는지

구하는 증명방식이다.

문제 접근

최적해의 순서가 있고, 최적해의 순서 중 $i$번째와 $i+1$번째 순서를 정할 때

어떻게 정할지 생각해보자.

$i-1$번째까지의 걸린 시간을 $L$이라고 하고,

$i$번째 구두를 먼저 수선한다고 하자. 그러면 $i$번째와 $i+1$번째 모두 지불하는 금액은

$L\cdot S_i+(T_i+L)\cdot S_{i+1}$

$i+1$번째 구두를 먼저 수선하면

$L\cdot S_{i+1}+(T_{i+1}+L)\cdot S_i$ 이 되고 이 중 더 공통된 부분을 제거해주고 비교해보면,

$i$번째 구두 수선이 최적해이려면 $T_i\cdot S_{i+1}$이 $T_{i+1}\cdot S_i$보다 작아야 한다.

즉 최적해의 순서는 $T_i/S_i$의 값이 작은 순서대로 배열한 것임을 알 수 있다.

따라서 작성한 코드는 다음과 같다.

#include <bits/stdc++.h>
using namespace std;

int main(){
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	int s,t;
	int n; cin >> n; vector<pair<double, int>> arr(n);
	for(int i=0;i<n;i++){cin >> t >> s;arr[i].first=(double)t/s;arr[i].second=i+1;}
	sort(arr.begin(),arr.end(),[](pair<double, int> l, pair<double, int> r)->bool{
		if(l.first==r.first) return l.second<r.second;
		else return l.first<r.first;
	});
	for(int i=0;i<n;i++) cout << arr[i].second << ' ';
	return 0;
}