문제 링크
문제
티어: 골드 1
알고리즘: 그리디, 정렬
지금 구두 수선공에게는 손님으로부터 주문 받고 제작해야 할 작업이 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)로 표시해야 한다. 모든 정수는 한 줄로 표시해야 하며, 각 작업은 공백 문자로 구분한다. 여러 가지 해답이 나올 수 있다면 오름차순 정렬에 의해 가장 첫 번째 해답을 출력한다.
풀이
최소 보상금을 지불하는 작업 순서를 출력해야 한다. 그러한 작업 순서가 여러 개라면 오름차순 정렬에 의해 가장 첫 번째 해답을 출력한다.
단순히 Si를 기준으로 생각해 볼 수 있다. Si가 큰 것을 우선적으로 하는 것이 최적 해를 보장해 주지 않을까? 그렇지 않다. Ti 값이 몇 인지에 따라서 오히려 Si가 작은 값이 최적 해를 보장할 수 있다. (Ti x Si의 곱이기 때문에)
그래서 두 요소를 활용해서 최적해를 결정해야 한다.
만약 2 1 3 4가 최적해라고 했을 때, 1 2 4 3에서 우리가 가장 먼저 고민해 볼 수 있는 부분은 1 번째, 2 번째 인덱스 중 어떠한 값이 우선으로 올 수 있고, 그 기준은 무엇인가이다.
만약 1 번째 2 번째가 변경되어야 한다면, 반드시 변경이 되어야 최적해를 보장함을 알 수 있다.
그러면, 그 뒤 4 3은 영향을 끼칠 수 있지 않을까?라는 의문이 드는데, 공식으로 나타내 보면, 2를 먼저하든 1를 먼저하든 결국 그 뒤는 같은 값을 가짐을 알 수 있다. 그래서 1 번째, 2 번째 중 어떠한 작업을 우선으로 할지 기준을 알아낸다면, 그 기준이 결국 정렬 기준이 될 것이다.
1 -> T1 S1
2 -> T2 S2
라고 했을 때
-
1 -> 2
1번을 먼저 작업하고, 2번을 작업한다면, 그 값은 T1 x S2이다. -
2 -> 1
2번을 먼저 작업하고, 1번을 작업한다면, 그 값은 T2 x S1이다.
만약 1 -> 2가 더 작다면
T1 x S2 < T2 x S1이며, T1 / S1 < T2 / S2 임을 알 수 있다.
그러니까 T/S가 작은 순으로 작업을 먼저 진행하는 것이 최적해임을 보장한다.
이를 T3 S3를 추가해서 증명해 봐도 같은 결론이 나온다. 앞에서 말했듯이 어차피 T1 S1, T2 S2를 비교할 때 뒤에 값은 영향을 받지 않기 때문에 이 두 작업을 비교해서 얻은 기준 T/S가 전체 작업의 정렬 기준이 된다.
그래서 T/S가 작은 순으로 정렬을 하는데, 같은 값이 있는 경우는 ind가 작은 값이 더 앞에 오게끔 한다. 그래야 최적 순서가 여러 가지인 경우에 오름차순 정렬에 의한 첫 번째 순서가 되기 때문이다.
소스 코드
import java.io.*;
import java.util.*;
class Job implements Comparable<Job>{
int ind;
double std;
Job(int ind, double std) {
this.ind = ind;
this.std = std;
}
@Override
public int compareTo(Job o) {
if(this.std < o.std) {
return -1;
} else if(this.std > o.std) {
return 1;
} else {
//같은 경우는 ind가 빠른 순
if(this.ind < o.ind) {
return -1;
} else if(this.ind > o.ind) {
return 1;
}
}
return 0;
}
}
public class Main {
static int N;
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
N = Integer.parseInt(br.readLine());
Job[] jobs = new Job[N];
for(int i=0; i<N; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
double t = Double.parseDouble(st.nextToken());
double s = Double.parseDouble(st.nextToken());
jobs[i] = new Job(i + 1, t / s);
}
Arrays.sort(jobs);
StringBuilder sb = new StringBuilder();
for(int i=0; i<N; i++) {
sb.append(jobs[i].ind).append(" ");
}
System.out.println(sb.toString().trim());
}
}