[BOJ][🟡5][백준#06068] 시간 관리하기

문제 출처

BAEKJOON Online Judge #6068

문제

성실한 농부 존은 시간을 효율적으로 관리해야 한다는 걸 깨달았다. 그는 N개의 해야할 일에 (1<=N<=1000) 숫자를 매겼다. (우유를 짜고, 마굿간을 치우고, 담장을 고치는 등의) 존의 시간을 효율적으로 관리하기 위해, 그는 끝내야만 하는 일 목록을 만들었다. 완성될 때 필요한 시간을 T_i(1<=T_i<=1,000) 라고 하며, 끝내야하는 시간을 S_i(1<=S_i<=1,000,000) 이라 한다. 농부 존은 하루의 시작을 t = 0으로 정했다. 그리고 일 할 때는 그 일을 마칠 때 까지 그 일만 한다.  존은 늦잠 자는 걸 좋아한다. 따라서 제 시간에 끝낼 수 있게 결정할 수 있는 한도에서 존이 가장 늦게 일어나도 되는 시간을 출력하라.

입력

첫 줄에는 일의 개수인 N을 받고 두 번째 줄부터 N+1줄까지 T_i와 S_i를 입력받는다. 

출력

존이 일을 할 수 있는 마지막 시간을 출력 하라. 존이 제시간에 일을 끝낼 수 없다면 -1 을 출력하라.

예제

입력

4
3 5
8 14
5 20
1 16

출력

2

My Sol

def main():
    N = int(input())
    Q = []
    for _ in range(N):
        t, e = map(int, input().split())
        Q.append((e, t))
    Q.sort()

    tt = 0
    ret = 1e8
    for i in range(N):
        e, t = Q[i]
        if tt+t > e: return -1
        tt += t
        ret = min(ret, e-tt)
    return ret

print(main())

잘 생각하면 간단하게 풀어낼 수 있는 문제였다.

1. 과제의 소요시간(t)과 마감기한(e)를 입력받아 Q에 저장한다.
2. 이를 정렬한다.
3. 따라서 마감기한이 가장 얼마 남지 않은 과제들부터 확인해서 0으로 초기화한 현재시간에 소요시간을 누적하며 나간다.
4. 이때 어떠한 과제에서 누적시간에 과제 소요시간을 더했을 때 마감시간을 넘어가버린다면 당장 시작해도 과제를 끝내지 못하므로 -1을 return한다.
5. 각 과제마다 누적시간에 소요시간을 더한 값(tt)이 마감기한보다 얼마나 작은지 매번 확인하는데, 이 차이 중 가장 작은 값이 결과값이 된다. 왜냐하면 0으로 초기화하고 뒤로 미루는데, 모든 과제는 마감기한 안에 해야하므로 그 최소 차이만큼 뒤로 미룬다고 생각하는 것이다. 그에 대한 절차를 작성한다.
6. 이를 반환하여 출력한다.

결과

맞았습니다!!

모범답안

출처

# empty