[자바] 백준 1263 - 시간 관리 (java)

목차

• 문제 : boj1263
• 필요 알고리즘
• 풀이
• 코드 : github

문제 : boj1263

 

 

필요 알고리즘

• 그리디
  
  • 잘 생각해보면 어! 이렇게 하면 되지 않나? 싶은 룰이 있다. 

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

 

풀이

  이 문제에서 물어보는건 모든 일을 끝낼 수 있는 가장 늦은 시간이다. 근데 좀 바꿔서 생각해보자. 애초에 모든 일을 끝낼 수 있나 없나를 어떻게 판단할 수 있을까?

 

  중요한건 S값이다. 언제 시작하는진 상관없고, 아무튼 N개의 일들에 대해 각 S값 이내로만 끝낼 수 있으면 모든 일이 가능한거다. 즉, 각각 (T,S)가 (2,7), (1,7), (3,7)인 3가지 일이 있다고 해보자. 어차피 S=7까지 셋 다 끝내야 한다. 어떤걸 먼저 하는지가 중요할까? 뭔가 S-T에 따라 해야할 것 같이 생겼지만, 어차피 1차원의 시간 내에 각각을 배치해야되고, S 이내로만 끝내면 되므로 S-T는 의미가 없다. 아래 그림처럼 T가 1인걸 먼저하든, 3인걸 먼저하든 상관 없다는 얘기다. 또 언제 하든 상관없다. 아무튼 S=7 이내로 끝내면 가능한거다.

 

  그럼 이제 가능한지 안한지는 생각해봤으니, 모든 일을 끝낼 수 있는 가장 늦은 시간은 어떻게 구할까? 간단하다. 최대한 빈 공간 없게 우측으로 붙여버리면 된다.

 

  그럼 이제 S가 다른 경우를 생각해보자. (T,S)가 (1,7), (2,5), (3,4) 이다. 이 경우엔 어떻게 배치해야할까? 전재조건은 최대한 우측으로 땡겨야 한다는 점이다. 그렇다면, S가 큰 것 부터 배치하는 것이 무조건 빈 공간을 최소화할 수 있다. 우선 S=7인걸 S=7에 둔다. 그리고 S=5인걸 S=5에 둔다. S=4인건 S=5인거가 T=2 이므로, S=4인 부분까지 사용하므로 거기에 못둔다. 그럼 그냥 빈 공간중 S=4 미만인 가장 큰 곳에 두면 된다! 빈 공간이 T만큼 안된다면? 그냥 -1 출력하고 종료하면 된다.

 

즉,

1. S가 동일하다면 뭘 먼저 두는진 상관없고 아무튼 최대한 우측으로 땡겨서 빈 공간에 둔다.

2. S가 다르다면 S가 큰 것 부터 최대한 우측에 배치하고 남는 공간에 그보다 S가 작은걸 두면 된다.

 

Arrays.sort(arr);	// S 내림차순 정렬

int pt = 1000000;
for (ToDo cur : arr) {
    pt = Math.min(pt, cur.s)-cur.t;	// Math.min(pt, cur.s)는 빈공간 중 S이하인 가장 큰 값이다.
    if (pt < 0) {	// 빈 공간이 없었다면 -1 출력하고 종료한다.
        System.out.println(-1);
        return;
    }
}

System.out.println(pt);

 

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class Main {

    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in), 1<<16);

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }

    private void solution() throws Exception {
        int n = Integer.parseInt(br.readLine());

        ToDo[] arr = new ToDo[n];
        while (n-->0) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int t = Integer.parseInt(st.nextToken());
            int s = Integer.parseInt(st.nextToken());

            arr[n] = new ToDo(t, s);
        }

        Arrays.sort(arr);

        int pt = 1000000;
        for (ToDo cur : arr) {
            pt = Math.min(pt, cur.s)-cur.t;
            if (pt < 0) {
                System.out.println(-1);
                return;
            }
        }

        System.out.println(pt);
    }
}

class ToDo implements Comparable<ToDo> {
    int t, s;

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

    @Override
    public int compareTo(final ToDo o) {
        return o.s-s;
    }
}