BOJ#1263 시간 관리

BOJ#1263 시간 관리

* 문제

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

* 풀이

일상 생활에서 흔히 하는 고민을 다룬 문제인 것 같습니다. 😅

(내일 무슨 무슨 일을 언제까지 해야 되니까, 몇시쯤 집에서 나가면 되겠구나! )

첫째 줄에 일의 개수 N,

그 다음 N개의 줄에 T와 S가 주어집니다. ( T : 필요한 시간, S : 납기 )

일단 S 기준으로 오름차순 정렬을 합니다. 내림차순으로 해도 상관없습니다.

3 5

8 14

1 16

5 20

0시 부터 일을 시작할 수 있으므로

가장 마지막 일(4번째 일)을 끝내기 위해서는 15시에는 일을 시작해야 합니다.

그리고 이것은 3번째 일에 영향을 주게 됩니다.

3 5

8 14

1 16 15

5 20

이어서 3번째 일을 끝내기 위해서는 14시에는 일을 시작해야 하고,

2번째 일의 납기는 14시 이므로 영향이 없겠네요.

마찬가지로 2번째 일을 끝내기 위해서는 6시에는 일을 시작해야 하는데

이것 또한 첫번째 납기보다는 크기 때문에 첫번째 일에 영향을 주지 않습니다.

☞ 같은 문제

6068번 - 시간 관리하기 https://www.acmicpc.net/problem/6068

---

* 나의 코드

https://github.com/stack07142/BOJ/blob/43730ad19a207fe5d67b71c0a158f65d86f05c19/BOJ%231263_TimeManage/src/Main.java

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

/**
 * BOJ#1263 시간 관리
 * https://www.acmicpc.net/problem/1263
 */

public class Main {

    static int N;
    static TimeTable[] table = new TimeTable[1001];

    public static void main(String[] args) throws IOException {

        // input
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        N = Integer.parseInt(br.readLine());

        for (int i = 0; i < N; i++) {

            StringTokenizer st = new StringTokenizer(br.readLine());

            table[i] = new TimeTable(Integer.parseInt(st.nextToken()), Integer.parseInt(st.nextToken()));
        }

        // solve

        // S(일을 끝내야 하는 시간)를 기준으로 오름차순 정렬
        Arrays.sort(table, 0, N);

        // time : 일을 끝마칠 수 있게, 가장 늦게 일을 시작하는 시간
        int time = table[N - 1].S - table[N - 1].T;
        for (int i = N - 2; i >= 0; i--) {

            // 다음 일을 위해, 현재 납기일 보다 더 빨리 끝마쳐야 한다면
            if (table[i].S > time) {

                table[i].S = time;
            }

            time = table[i].S - table[i].T;
        }

        if (time < 0) System.out.println(-1);
        else System.out.println(time);
    }
}

class TimeTable implements Comparable<TimeTable> {

    int T;
    int S;

    TimeTable(int T, int S) {

        this.T = T;
        this.S = S;
    }

    @Override
    public int compareTo(TimeTable o) {

        return this.S < o.S ? -1 : this.S == o.S ? this.T <= o.T ? -1 : 1 : 1;
    }
}