[백준] 1263번: 시간 관리 문제 풀이

문제

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

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

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

입력

첫째 줄에 일의 수 N이 입력되고 다음 N개의 줄에 대해 i+1번째 줄에는 i번째 일에 대한 Ti와 Si가 입력된다.

출력

진영이가 일을 모두 끝마칠 수 있는 가장 늦은 시간을 출력한다. 만약 0시부터 시작하여도 일을 끝마칠 수 없다면 -1을 출력한다.

문제 풀이
1. 각 스케줄을 완료할 때마다 소요시간의 합을 구한다.
2. 소요시간의 합이 해당 스케줄의 제한시간보다 크면(스케줄을 처리할 수 없으면), 하루 일정의 시작 시간에서 한시간을 빼고 출력한다.
3. 하루의 스케줄까지 처리할 수 있으면 (소요시간의 합이 해당 스케줄보다 작으면) 하루 일정의 시작 시간을 한시간씩 늦춘다.

전체 코드

N = int(input())
schedule = []

# 일정 소요시간과 완료해야하는 시간 schedule에 저장
for _ in range(N):
    T, S = map(int, input().split())
    schedule.append([T, S])

# 일정을 완료해야하는 순으로 정렬
schedule = sorted(schedule, key=lambda x:x[1])

#일정 시작시간
time = 0
while 1:
    # time만큼 늦게 시작함
    sumTime = time

    #전체 일정들에 대해
    for t, s in schedule:
        # 해당 일정을 제 시간안에 처리할 수 있으면 소요시간+t
        if sumTime+t <= s:
            sumTime += t
        else:
            # 늦게 시작했을 때 완료하지 못하면
            # 시작 시간보다 1시간 일찍 시작하는것으로 출력
            # 0시에 시작했는데도 완료하지 못하면 -1 출력
            print(time-1)
            exit()
    time += 1