[백준 1263번 / java] 시간 관리

문제

1263번: 시간 관리 (acmicpc.net)

1. 할 일 N개
2. Ti 시간 걸리는 일을 Si시 내에 마쳐야 함
3. 0시부터 활동 가능
4. 한 번에 1개의 일만
5. 최대한 늦게 일을 시작할 수 있는 시간을 찾기

풀이

그리디 문제이다. 

최대한 늦게 일을 시작해야 하므로, 마감 시간이 가장 빠른 일을 끝내기 위해서는 적어도 몇 시부터 일을 시작해야 하는지 부터 고려했다. 

4
3 5
8 14
5 20
1 16

예를 들어 위 예제에서는 마감 시간이 5시가 가장 빠르고, 이 일을 끝내는 데 3시간 걸리므로 적어도 2시에는 일을 시작해야 한다. 그런데 최대한 늦게 일을 시작해야 하므로 2, 3, 4시에는 마감 시간이 5시인 일을 반드시 해야 한다. 

 

다음으로 빠른 마감 시간은 14시이고, 이 일을 끝내는 데 8시간이 걸린다. 이미 일을 2시에 시작했으므로, 2시 이후부터 14시 전까지 8시간의 일을 끝내면 된다. 단, 2, 3, 4시는 이미 자리가 찼으므로 제외한다. 

 

이런 식으로 마감 시간이 가장 빠른 일부터 차례로 일할 시간을 배정한다.

배정 시간은 겹치지만 않으면 되므로, 마감 시간 기준 앞으로 한 칸씩 이동하면서 아직 배정 안 된 자리가 발견되면 그 시간을 배정하도록 했다. 

 

끝내야할 시간 중 가장 이른 시간 선택 -> 인덱스를 -1하며 해당 시간 이전시간에 아직 방문하지 않은 곳이 있는지 확인, 걸리는 시간 만큼 방문체크 ->이때, 0시부터 시작해도 일을 끝마칠 수 없다면 -1을 출력

코드

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

public class Main {
    static List<Task> list;
    static boolean[] check;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        int N = Integer.parseInt(br.readLine());
        list = new ArrayList<>();
        check = new boolean[1000001]; //시작시간 선택 여부 체크
        for(int i=0; i<N; i++){
            st = new StringTokenizer(br.readLine());
            int t = Integer.parseInt(st.nextToken());
            int s = Integer.parseInt(st.nextToken());
            list.add(new Task(t, s));
        }
        //끝내야할 시간(s) 중 가장 이른 시간 선택
        Collections.sort(list, (o1, o2) -> o1.s- o2.s);
        bw.write(manage()+" ");

        bw.close();
    }

    static int manage(){
        int ans = 0;
        for(int i=0; i<list.size(); i++){
            int earliestTime = list.get(i).s; //끝내야할 시간
            int takingTime = list.get(i).t; //걸리는 시간
            int count = 0; //걸리는 시간 저장 횟수

            for(int j=earliestTime-1; j>=0; j--){
                if(count == takingTime)
                    break;
                if(!check[j]){
                    check[j] = true;
                    count++;
                }
            }
            //0까지 다 찾았는데도 아직 걸리는 시간이 남아있다면 -1출력
            if(count < takingTime){
                return -1;
            }
        }
        for(int i=0; i<check.length; i++){
            if(check[i]){
                ans = i;
                break;
            }
        }
        return ans;
    }
}
class Task{
    int t, s;
    public Task(int t, int s){
        this.t = t;
        this.s = s;
    }
}

Note

• 스터디 피드백
  • list를 정렬할 때 collections.sort보다 list.sort가 더 편하다는 의견이 있었다. reverse만 주면 역순정렬도 쉽게 구현할 수 있기 때문.
  • collections.sort에 람다식으로 정렬 기준을 줄 때, -1은 그대로, 1은 자리를 바꾼다고 생각하면 쉽다. 예를 들어 5-5=1이므로 자리를 바꿔야 한다.
• 같은 그리디인데, 다른 방법으로 푼 경우
  • 풀이 1
    • 나는 boolean배열로 방문 체크를 하며 시간을 배정했는데, 시작 시간과 마감 시간의 값만 가지고 그 차이를 구해서 현재까지 배정된 시간을 빼는 식으로 구현함
  • 풀이 2
    • 마감 시간이 가장 늦은 일부터 역순으로 일을 배정하는 방법
    • 일을 마감 시간에 맞춰서 끝내는 것이 가장 그리디한 선택이라는 접근
    • 현재까지 선택된 일을 끝내기 위해 걸리는 시간을 변수로 두고, 시간이 1씩 앞으로 갈 때마다 변수 -1

    • 4
      3 5
      8 14
      5 20
      1 16

      가장 늦은 마감 시간은 20시, 일을 끝내는 데 5시간 걸림. 변수를 5로 두고, 앞으로 한 칸씩 이동하며 변수-1해준다. 16시를 만나면 변수에 1을 더해준다. 16시까지 끝내야 하는 일은 1시간이기 때문.