[백준 - 6068][GOLD 5][해설 X] - 시간 관리하기 (JAVA)

문제 링크

---

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

 

문제

---

성실한 농부 존은 시간을 효율적으로 관리해야 한다는 걸 깨달았다. 그는 N개의 해야할 일에 (1<=N<=1000) 숫자를 매겼다. (우유를 짜고, 마굿간을 치우고, 담장을 고치는 등의)

존의 시간을 효율적으로 관리하기 위해, 그는 끝내야만 하는 일 목록을 만들었다. 완성될 때 필요한 시간을 T_i(1<=T_i<=1,000) 라고 하며, 끝내야하는 시간을 S_i(1<=S_i<=1,000,000) 이라 한다. 농부 존은 하루의 시작을 t = 0으로 정했다. 그리고 일 할 때는 그 일을 마칠 때 까지 그 일만 한다. 

존은 늦잠 자는 걸 좋아한다. 따라서 제 시간에 끝낼 수 있게 결정할 수 있는 한도에서 존이 가장 늦게 일어나도 되는 시간을 출력하라.

 

입력

---

첫 줄에는 일의 개수인 N을 받고

두 번째 줄부터 N+1줄까지 T_i와 S_i를 입력받는다. 

 

출력

---

존이 일을 할 수 있는 마지막 시간을 출력 하라. 존이 제시간에 일을 끝낼 수 없다면 -1 을 출력하라.

 

해결 코드

---

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());
		
        //마감기한이 가장 늦은 순서로 정렬
        PriorityQueue<Task> pq = new PriorityQueue<>((a,b)-> b.deadine - a.deadine);

        for(int i=0;i<N;i++){
            StringTokenizer st = new StringTokenizer(br.readLine());

            int time = Integer.parseInt(st.nextToken());
            int deadline = Integer.parseInt(st.nextToken());

            pq.add(new Task(time, deadline));
        }

		//가장 늦게 끝내도 되는 작업을 기준으로 현재 시간 초기화
        Task last = pq.poll();
        int currentTime = last.deadine - last.time;
		
        //마감시간에 딱 맞추거나 빈시간이 없도록 현재시간을 갱신
        while(!pq.isEmpty()){
            Task task = pq.poll();

            currentTime = Math.min(currentTime,task.deadine) - task.time;
        }
		
        //음수면 -1로 고정
        currentTime = currentTime < 0 ? -1 : currentTime;

        System.out.println(currentTime);
    }
}
class Task{
    int time;
    int deadine;

    public Task(int time, int deadine){
        this.time = time;
        this.deadine = deadine;
    }
}

 

 

실행 결과

---

 

팁

---

• 어떤 조건일 때 가장 최대의 이득을 보는지 생각하자.
• 조건이 위배되는 경우를 생각해서 예외를 찾자