[Boj_1263] 시간 관리

📎 문제 링크

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

 

▸ 문제

진영이는 캠프 조교를 온 후 효율적으로 시간 관리를 해야 한다는 것을 깨달았다. 진영이는 하루에 해야 할 일이 총 N개가 있고 이 일들을 편하게 1번부터 N번까지 차례대로 번호를 붙였다.

진영이는 시간을 효율적으로 관리하기 위해, 할 일들에 대해 끝내야할 시간과 걸리는 시간을 적은 명단을 만들었다. 즉, 이 명단은 i번째 일은 일을 처리하는데 정확히 Ti 시간이 걸리고 Si 시 내에 이 일을 처리하여야 한다는 것을 담고 있다. 진영이는 0시부터 활동을 시작할 수 있고, 두 개 이상의 일을 같은 시간에 처리할 수 없다.

진영이가 바라는 점은 최대한 늦잠을 자는 것이다. 문제는 이러한 진영이를 도와 일들은 모두 마감시간 내에 처리할 수 있는 범위 내에서 최대한 늦게 일을 시작할 수 있는 시간이 몇 시인지 알아내는 것이다.

 

▸ 입력

첫째 줄에 일의 수 N이 입력되고 다음 N개의 줄에 대해 i+1번째 줄에는 i번째 일에 대한 Ti와 Si가 입력된다.

 

▸ 출력

진영이가 일을 모두 끝마칠 수 있는 가장 늦은 시간을 출력한다. 만약 0시부터 시작하여도 일을 끝마칠 수 없다면 -1을 출력한다.

 

▸ 제한

• 1 ≤ N ≤ 1,000
• 1 ≤ Ti ≤ 1,000
• 1 ≤ Si ≤ 1,000,000

 

📍 문제 정보

• 🥇  문제 레벨 : 골드 5
• 🔔  문제 유형 : 그리디 알고리즘, 정렬
• 💬  풀이 언어 : JAVA

 

🤔 문제 풀이

이 문제는 정렬과 그리디 알고리즘으로 해결할 수 있다.

핵심은, 모든 일을 마감시간 내에 끝낼 수 있는 범위 내에서 가능한 가장 늦게 일을 시작하는 것이다.

이를 위해 마감 시간이 늦은 작업부터 차례대로 처리하는 것에 초점을 맞춰 풀었다.

 

먼저 각 작업의 마감 시간을 기준으로 내림차순 정렬한다.

만약 마감 시간이 같은 작업이 있다면, 어느 것을 선택해도 된다.

 

먼저 초기 시작 시간을 가장 늦은 작업의 마감 시간으로 설정한다.

정렬된 작업들을 순서대로 처리하면서, 각 작업이 마감 시간 내에 끝나도록 필요한 시작 시간을 계산하고,

이를 기준으로 이전 작업이 시작할 수 있는 가장 늦은 시간을 계속 갱신한다.

 

이때, 만약 시작 시간이 0시간보다 이전으로 내려가면

진영이가 활동을 시작할 수 없는 시간이므로  -1을 출력한다.

 

위 풀이를 코드로 작성해 보면 아래와 같다.

 

✔ 코드

메모리 : 12136KB
시간 : 76ms

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.StringTokenizer;

public class Main {
    static public class Time implements Comparable<Time> {
        int processTime; int end;
        public Time(int processTime, int end) {
            this.processTime = processTime; this.end = end;
        }
        @Override
        public int compareTo(Time o) {
            // 종료 시간이 가장 늦은 일을 가장 뒤에 배치
            return o.end - this.end;
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st;
        List<Time> works = new ArrayList<>();
        int t, s; // 일 처리 시간, 제한 시간
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine());
            t = Integer.parseInt(st.nextToken());
            s = Integer.parseInt(st.nextToken());

            works.add(new Time(t, s));
        }
        Collections.sort(works);

        int time = works.get(0).end; // 최댓값
        for (int i = 0; i < n; i++) {
            time = Math.min(works.get(i).end, time) -  works.get(i).processTime;
            if (time < 0) {
                time = -1;
                break;
            }
        }

        System.out.println(time);

        br.close();
    }
}

 

해결 완료 ! 🔥

 

여행 갔다 오느라 지난주 내내 스트릭 채우기용 문제만 풀어서 풀이를 생각하는데 꽤 오랜 시간이 걸렸다.
그런 김에 한 번 더 정리할 겸 블로그에 포스팅까지 완료 !

역시 오랜만에 문제 풀면 오랜 시간이 걸리는 것 같다.. 꾸준히 풀려고 노력해야지 ! ⭐