[Algorithm] boj_14908 (Greedy)

문제

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

접근 방법

최저 보상금을 지불하는 작업 순서를 구하는 문제이다.

• 미완료 작업 개수가 많더라도, 보상금이 작을수 있음

-> 보상/시간 비율이 큰 순서로 정렬해야 한다.

ex) 만일 t1.시간 * t2.보상 < t2.시간 * t1.보상 이라면, t1을 먼저 수행해야한다.

즉, 위 기준으로 내림차순 정렬, 만일 값이 같다면 인덱스 기준 오름차순 정렬을 수행하면 된다!

코드

import java.io.*;
import java.util.*;

public class boj_14908_greedy {

    static int N;
    static Task[] tasks;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        tasks = new Task[N];

		//input
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int time = Integer.parseInt(st.nextToken());
            int fee = Integer.parseInt(st.nextToken());
            tasks[i] = new Task(i, time, fee);
        }

		//sort
        Arrays.sort(tasks, (o1, o2) -> {
            long lhs = (long) o1.time * o2.fee; //o2의 최종 보상료
            long rhs = (long) o2.time * o1.fee; //o1의 최종 보상료

            if (lhs != rhs) return Long.compare(lhs, rhs);
            return Integer.compare(o1.idx, o2.idx);
        });

        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < N; i++) {
            sb.append(tasks[i].idx + 1).append(" ");
        }

        System.out.println(sb);
    }

    private static class Task {
        int idx, time, fee;

        Task(int idx, int time, int fee) {
            this.idx = idx;
            this.time = time;
            this.fee = fee;
        }
    }
}