[알고리즘] 백준 1263 파이썬 - 시간 관리

 

1263번: 시간 관리

문제

진영이는 캠프 조교를 온 후 효율적으로 시간 관리를 해야 한다는 것을 깨달았다. 진영이는 하루에 해야 할 일이 총 N개가 있고 이 일들을 편하게 1번부터 N번까지 차례대로 번호를 붙였다.

진영이는 시간을 효율적으로 관리하기 위해, 할 일들에 대해 끝내야할 시간과 걸리는 시간을 적은 명단을 만들었다. 즉, 이 명단은 i번째 일은 일을 처리하는데 정확히 Ti 시간이 걸리고 Si 시 내에 이 일을 처리하여야 한다는 것을 담고 있다. 진영이는 0시부터 활동을 시작할 수 있고, 두 개 이상의 일을 같은 시간에 처리할 수 없다.

진영이가 바라는 점은 최대한 늦잠을 자는 것이다. 문제는 이러한 진영이를 도와 일들은 모두 마감시간 내에 처리할 수 있는 범위 내에서 최대한 늦게 일을 시작할 수 있는 시간이 몇 시인지 알아내는 것이다.

 

 

문제풀이

import sys
input = sys.stdin.readline
arr=[]
#01
for _ in range(int(input())):
    arr.append(list(map(int,input().split())))
arr.sort(key=lambda x:x[1])
tmp=0
#02
for i in range(len(arr)-1,-1,-1):
    if tmp==0:
        tmp=arr[i][1]-arr[i][0]
    else:
        if tmp>arr[i][1]:
            tmp=arr[i][1]-arr[i][0]
        else:
            tmp=tmp-arr[i][0]
#03
if tmp<0:
    print(-1)
else:
    print(tmp)

- #01 : 입력받은 대로 arr에 저장해준다. arr의 [1] 기준 즉 2번째 값 기준으로 정렬한다.

- #02 : 리스트를 뒷 순서부터 얻기 위한 for문을 작성한 후 

           tmp에 가장 마지막 값의 arr[i][1] - arr[1][0]을 저장한다.

           즉 tmp에는 마지막에서 부터 일을 차질없이 끝내기 위해 일을 시작해야할 시간을 저장한다.

 

           이후 tmp 값이 0이 아니면, tmp와 arr[i][1]의 값을 비교한다.

           만약 tmp가 크다면 가장 마지막 일을 해도 그 전 일에 차질이 없다는 것이다.

           그렇다면 tmp에는 현재 일을 문제없이 끝내기 위해 일을 시작해야할 시간을 저장한다.

           그렇지 않다면 tmp에 arr[i][0]의 시간을 빼준다.

- #03 : tmp가 0보다 작으면 -1을 출력 그렇지 않다면 tmp를 출력해준다.

 

 

+ 예를 들어 [8,24] -> [6,18]이라고 해보자.

   첫번째 일을 끝내려면 16시에는 일을 시작해야 한다.

   두번째 일을 끝내려면 12시에는 일을 시작해야 한다.

   하지만 첫번째 일은 16시부터 시작해야 24시에 끝낼 수 있다.

   즉 16~18시까지는 첫번째 일을 진행해야 한다.

   다시 말해, 두번째 일을 10시부터는 시작해야

   10시 + 6시간 = 16시 -> 16시+8시간 = 24시 안에 일을 끝낼 수 있다.