[baekjoon] 1263번 시간 관리

출처

---

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

1263번: 시간 관리

 

 

문제

---

진영이는 캠프 조교를 온 후 효율적으로 시간 관리를 해야 한다는 것을 깨달았다.

진영이는 하루에 해야 할 일이 총 N개가 있고 이 일들을 편하게 1번부터 N번까지 차례대로 번호를 붙였다.

진영이는 시간을 효율적으로 관리하기 위해, 할 일들에 대해 끝내야할 시간과 걸리는 시간을 적은 명단을 만들었다.

즉, 이 명단은 i번째 일은 일을 처리하는데 정확히 Ti 시간이 걸리고 Si 시 내에 이 일을 처리하여야 한다는 것을 담고 있다.

진영이는 0시부터 활동을 시작할 수 있고, 두 개 이상의 일을 같은 시간에 처리할 수 없다.

진영이가 바라는 점은 최대한 늦잠을 자는 것이다.

문제는 이러한 진영이를 도와 일들은 모두 마감시간 내에 처리할 수 있는 범위 내에서

최대한 늦게 일을 시작할 수 있는 시간이 몇 시인지 알아내는 것이다.

 

 

입력

---

첫째 줄에 일의 수 N이 입력되고 다음 N(1≤N≤1,000)개의 줄에 대해

i+1번째 줄에는 i번째 일에 대한 Ti(1≤Ti≤1,000)와 Si(1≤Si≤1,000,000)가 입력된다.

 

 

출력

---

진영이가 일을 모두 끝마칠 수 있는 가장 늦은 시간을 출력한다.

만약 0시부터 시작하여도 일을 끝마칠 수 없다면 -1을 출력한다.

 

 

풀이 및 코드

---

처음엔 문제 정의와 입력간의 괴리로 인해 물음표가 나왔던 문제였다.

하루에 해야 할 일이라고 언급했음에도 일이 걸리는 시간 Si의 범위가 1≤Si≤1,000,000 이랬기 때문.

그래도 문제를 풀기 위해 진영이의 하루는 24시간이 아닌 1,000,000,000시간 이상이겠거니 생각하고 풀었다.

 

이해하기 편하게 끝내야 할 시간 순으로 정렬해 준 뒤, Greedy하게 해결해주면 간단히 풀 수 있는 문제였다.

 

1. 첫 작업을 마무리 할 수 있으면서도 가장 늦게 일어나는 시간을 init으로 선언한다.

2. forloop로 n개의 작업을 돌며 작업 수행 후 현재 시간을 기록한다.

   2 - (1) 만약 i번째 작업을 수행했는데 현재 시간이 끝내야 하는 시간을 넘게 되면,

            현재 시간과 끝내야 하는 시간의 차를 다음 라운드에서 빼주면서 기상 시간을 줄여 나간다.

   2 - (2) 모든 작업을 수행할 수 있으면 현재 라운드의 기상 시간 출력

   2 - (3) 기상 시간이 0시 밑이 될 경우, -1 출력

 

import sys

input = sys.stdin.readline
n = int(input())
task = []
for _ in range(n):
    a,b = map(int, input().split())
    # (끝내야 하는 시간, 걸리는 시간) 쌍으로 입력
    task.append((b,a))
# 끝내야 하는 시간 기준으로 정렬
task.sort()

# 가장 먼저 끝내야 하는 작업의 끝내야 하는 시간 - 걸리는 시간 init
init = task[0][0] - task[0][1]
# 시간 초과분을 담아줄 gap
gap = 0

while True:
    # 매 라운드마다 현재 시간(시작 시간)은 init - gap
    now = init - gap
    # 현재 시간이 0보다 작으면
    # 0시부터 작업해도 일을 끝낼 수 없음
    if now < 0: 
        print(-1)
        break
    else:
        for i in range(n):
            now += task[i][1]
            # 만약 현재 시간이 i번째 작업을 끝내야하는 시간보다 크면 break
            # 이 때 현재 시간과 끝내야하는 시간의 차를
            # 다음번 시작시간에서 빼 주면서 업데이트
            if now > task[i][0]:
                gap += now - task[i][0]
                break
        # 모든 작업이 가능하면 현재 라운드의 시작 시간 출력
        else:
            print(init - gap)
            break