[백준 6068번] 파이썬 - 시간 관리하기

백준 6068 - 시간 관리하기

시간 제한 1초, 메모리 제한 128MB

# 조건

• 성실한 농부 존은 시간을 효율적으로 관리해야 한다는 걸 깨달았다.
• 그는 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을 출력하라.

# 접근 방법

• 최대한 늦게 일어나는게 중요하지만, 모든 일을 끝마칠 수 있는지 여부도 체크해야 한다.
• 우선, 입력받는 걸리는 시간, 마감 시간을 time 리스트에 저장해준다.
• 이후, 가장 마감 시간이 늦고, 걸리는 시간이 큰 값을 기준으로 내림차순 정렬해준다.
• 이후 현재 t를 time[0][1]로 설정해준 후 for문으로 모든 값을 순회한다.
  • 만약 t가 마감시간보다 크다면 마감시간 - 걸리는 시간으로 갱신해준다.
  • 그렇지 않다면 t - 걸리는 시간 해준다.
• 반복문이 끝나기 전에 t가 0이하가 된다면 -1을 출력, 아니라면 t를 출력해주면 된다.

import sys  
sys.stdin = open('input.txt')  
input = sys.stdin.readline  

N = int(input())  
time = []  
for _ in range(N):  
    a, b = map(int, input().split())  
    time.append((a, b))  
time.sort(key=lambda x:(x[1], x[0]), reverse=True)  
t = time[0][1]  

for i, j in time:  
    if t >= j:  
        t = j-i  
    else:  
        t -= i  
    if t < 0:  
        print(-1)  
        break  
else:  
    print(t)