백준 1263번: 시간 관리

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

문제 풀이

그리디

answer = 현재 확인하는 일을 마감시간에 끝날 수 있도록 하는 일의 시작 시간

일을 마감시간 기준 내림차순으로 정렬 후 일의 마감시간과 answer를 비교해 answer가 더 크다면 answer에 마감시간 대입 후 answer에서 일의 걸리는 시간을 뺌

이를 모든 일에 대해 반복한 후 answer의 값이 모든 일을 끝마칠 수 있는 제일 늦게 일을 시작하는 시간이므로 이 값이 0보다 작을때는 -1 출력, 아니면 그대로 값을 출력하면 정답

풀이 설명

일을 하는데 걸리는 시간과 마감시간이 있고, 두개 이상의 일을 같은 시간에 처리할 수 없을 때 모든 일을 마감시간 내에 처리할 수 있도록 최대한 늦게 일을 시작하는 것은 일을 하나하나 볼때 최대한 일을 마감시간에 끝내도록 처리해야 하는 것이다.

즉, 일을 최대한 늦게 시작할 수 있는 시간은 마감시간에서 걸리는 시간을 뺀 시간이 된다.

여기서 확인해야 할 것은 현재 일이 있고 이 일이 끝난 다음에 처리해야 할 일이 있을 때 현재 일이 마감시간에 끝나도록 늦게 시작하면 다음 일을 마감 시간 전에 끝낼 수 있는지를 확인해야 한다는 점이다.

만약 다음에 처리해야 할 일이 걸리는 시간이 충분히 짧아서 현재 일을 마감시간에 맞게 끝내도 다음 일을 처리할 수 있다면 괜찮지만, 그렇지 않다면 다음 일을 마감시간에 끝내기 위해 시작해야 하는 시간이 현재 일의 마감시간보다 빠른 것이고, 이에 따라 모든 일을 마감시간 내에 끝낼 수 있도록 현재 일을 처리하려면 현재 일의 마감시간보다 더 빠른 시간에 끝내야 한다는 것이다.

즉, 현재 일보다 마감시간이 늦은 일이 현재 시간의 실질적인 마감시간을 앞당길 수 있기 때문에 일을 마감시간이 늦은 일부터 확인해야 다른 일이 모든 일을 처리할 수 있도록 하는 실제 마감시간을 구할 수 있다.

따라서 모든 일을 처리할 수 있는 범위 내에서 최대한 일을 늦게 시작할 수 있는 시간을 구하기 위해 일을 마감시간 기준 내림차순으로 정렬하고, 앞의 일을 마감시간에 끝낼 수 있는 시간과 현재 일의 마감시간을 계속 비교하며 더 이른 시간에 일을 끝낼 수 있도록 일을 시작하는 시간을 구하면 이 값이 모든 일을 처리할 수 있도록 일을 시작해야 하는 최대한 늦은 시간이 된다.

따라서 이 값이 0보다 작게 되면 모든 일을 처리할 수 없는 것이므로 -1을 출력하면 되고, 0 이상이라면 이 값이 모든 일을 처리할 수 있는 최대한 늦게 일을 시작하는 시간이므로 값을 출력해주면 정답이 된다.

소스 코드

import java.util.StringTokenizer

fun main(){
    val N = readLine()!!.toInt()
    val arr = ArrayList<IntArray>()
    repeat(N){
        val st = StringTokenizer(readLine())
        val t = st.nextToken().toInt()
        val s = st.nextToken().toInt()
        arr.add(intArrayOf(t, s))
    }
    arr.sortWith{o1, o2 -> o2[1] - o1[1]}
    var answer = arr[0][1]
    for(work in arr){
        if(answer > work[1]){
            answer = work[1]
        }
        answer -= work[0]
    }
    if(answer < 0){
        println(-1)
    } else {
        println(answer)
    }
}