[백준] 1263번. 시간 관리(JAVA)

문제

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

---

풀이(15분)

import java.io.*;
import java.math.BigDecimal;
import java.util.*;

public class Main {

    // 정렬 시켜두고 뒤에서부터 쪼여가면서 찾자

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st;

        int n = Integer.parseInt(br.readLine());
        ArrayList<Work> works = new ArrayList<>();
        for(int i = 0; i < n; i++){
            st = new StringTokenizer(br.readLine());
            int turnaround = Integer.parseInt(st.nextToken());
            int finishTime = Integer.parseInt(st.nextToken());
            works.add(new Work(turnaround, finishTime));
        }

        Collections.sort(works, ((o1, o2) -> {
            if(o1.finishTime != o2.finishTime){
                return o2.finishTime - o1.finishTime; // 마쳐야하는 시간이 다르면 마쳐야하는 시간이 느린 것부터
            }
            return o1.turnaround - o2.turnaround; // 마쳐야하는 시간이 같다면 걸리는 시간이 적은 것부터
        }));

        // 현재 시간
        // 초기 설정은 제일 마지막의 (종료시간 - 소요 시간)
        int nowTime = works.get(0).finishTime - works.get(0).turnaround;


        for(int i = 1; i < n; i++){
            Work cur = works.get(i);
            if(nowTime >= cur.finishTime){ // 시간에 여유가 있다면
                nowTime = cur.finishTime - cur.turnaround; // (종료시간 - 소요 시간)
                continue;
            }
            // 끝나는 시간에 딱 맞춰서 작업을 못한다면
            nowTime -= cur.turnaround; // (현재 시간 - 소요 시간)
        }
        if(nowTime < 0){
            System.out.println(-1);
            return;
        }

        System.out.println(nowTime);

    }

    static class Work{
        int turnaround;
        int finishTime;

        public Work(int turnaround, int finishTime){
            this.turnaround = turnaround;
            this.finishTime = finishTime;
        }
    }
}

---

문제 풀이 전략

 

결국 종료 시간을 최대한 지켜가며 진행하는 것이 중요한 문제이다.

• 만약 소요 시간을 진행한 후에도 시간적 여유가 있다면 종료 시간에 최대한 붙여서 진행해야 한다.
• 그렇게 해야 최대한 늦잠을 잘 수 있다!!

1. 종료 시간 순으로 정렬한다.
   1. 종료 시간이 동일하다면 소요 시간이 짧은 것이 우선이다.
   2. 굳이 a와 동일하게 소요 시간이 짧은 것을 우선 정렬할 필요는 없다.
2. 초기 설정을 제일 마지막의 (종료 시간 - 소요 시간)으로 잡는다.
3. 시간에 여유가 있다면 (종료 시간 - 소요 시간)을 진행한다.
4. 시간에 여유가 없다면 (현재 시간 - 소요 시간)을 한다.
5. 만약 현재 시간이 0보다 작다면 불가능한 것으로 -1을 출력한다.