[백준 1263] 시간 관리 (Python)

www.acmicpc.net/problem/1263

1263번: 시간 관리

 

문제풀이

N : 입력값

arr : i번째 작업의 (완료시간, 작업이 걸리는 시간)

 

작업의 완료 시간을 기준으로 가장 늦게 완료해도 되는 작업부터 시작해서 다른 일들의 작업 시간을 탐색하면서 시작 시간을 갱신하는 그리디 알고리즘으로 해결할 수 있다.

 

1. 작업의 완료 시간을 기준으로 역순으로 정렬하기

 

2. 첫 번째 작업의 최대 시작 시간을 시작으로 나머지 작업들 확인하기

- i번째 일을 끝마쳐야 하는 시간이 현재 시간보다 앞선다 => i번째 일을 시작할 수 있는 가장 늦은 시간으로 시작 시간 갱신

- i번째 일을 끝마쳐야 하는 시간이 현재 시간보다 앞서지 않는다 => 현재 시간에서 i번째 일의 작업 시간만큼 감소

 

코드

import sys

if __name__ == '__main__':
    N = int(input())
    arr = []
    for _ in range(N):
        a, b = map(int, sys.stdin.readline().split())
        arr.append((b, a))
    # 가장 늦은 시간에 해결해도 되는 일 순으로 역순 정렬
    arr.sort(reverse=True)
    ans = arr[0][0] - arr[0][1]
    for i in range(1, N):
        # i번째 일을 끝마쳐야 하는 시간이 현재 시간보다 앞선다면
        # 시작 시간 갱신 : i번째 일을 시작할 수 있는 가장 늦은 시간
        if ans > arr[i][0]:
            ans = arr[i][0] - arr[i][1]
        # i번째 일을 끝마쳐야 하는 시간이 현재 시간보다 앞서지 않는다면
        # 시작 시간 갱신 : i번쨰 일을 완료하는데 걸리는 시간만큼 현재 시간에서 감소
        else:
            ans -= arr[i][1]
    print(ans if ans >= 0 else -1)

 

 

결과

 

 

문제풀이나 코드에서 이상한 부분 지적은 언제나 환영합니다!