[백준] 14908번 구두 수선공

문제 설명

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

문제 풀이

• 문제 조건에 맞게 그리디한 정렬을 이용하여 풀이하였다.
• 작업을 정렬할 때 다음과 같은 비교 기준을 사용한다.

  • 1번 작업과 2번작업을 비교할 때 다음을 기준으로 비교한다.
    - T1 x S2 : 1번작업을 진행했을 때 내야하는 보상금 (risk1)
    - T2 x S1 : 2번작업을 진행했을 때 나야하는 보상금 (risk2)
    - risk1 < risk2 : 1번이 더 우선순위를 가짐
    - risk1 > risk2 : 2번이 더 우선순위를 가짐
    • risk1 = risk2 : 번호가 작은 작업이 우선순위를 가짐

• 위 정렬 조건을 이용하여 단순 정렬 후 출력하면 된다.

소스 코드 (JAVA)

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

class Main {

    static class Work implements Comparable<Work>{
        int t, s, n;

        public Work(int t, int s, int n) {
            this.t = t;
            this.s = s;
            this.n = n;
        }

        @Override
        public int compareTo(Work o) {
            int riskThis = this.t * o.s;
            int riskOther = this.s * o.t;
            if (riskThis < riskOther) return -1;
            else if(riskThis > riskOther) return 1;
            else return this.n - o.n;
        }
    }

    static BufferedReader br;
    static BufferedWriter bw;

    static int N;
    static List<Work> workList = new ArrayList<>();

    public static void solve() throws IOException {
        //우선 순위대로 정렬
        Collections.sort(workList);
        for (int i = 0; i < workList.size(); i++)
            bw.write(workList.get(i).n + " ");
        bw.write("\n");
        bw.flush();
    }

    public static void input() throws IOException {
        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        N = Integer.parseInt(br.readLine());
        for (int i = 0; i < N; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int t = Integer.parseInt(st.nextToken());
            int s = Integer.parseInt(st.nextToken());
            workList.add(new Work(t, s, i+1));
        }
    }

    public static void main(String[] args) throws IOException {
        input();
        solve();
    }
}