문제 바로가기
문제:
성실한 농부 존은 시간을 효율적으로 관리해야 한다는 걸 깨달았다. 그는 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 을 출력하라.
풀이:
import sys
n = int(input())
s = sorted([list(map(int,input().split(" "))) for _ in range(n)], key = lambda x:x[1])
# [걸리는시간, 끝내야 하는 시간]
res = 0
result = 1e9
for time, limit in s:
res += time
result = min(result, limit-res) #limit - res를 계산하여 현재 일을 제 시간에 끝낼 수 있는 가장 늦은 시간을 찾습니다
if limit < res:
print(-1)
exit()
print(result)
그리디 알고리즘을 사용한다.
끝내야 하는 시간 기준으로 오름차순 해두어서 시간을 계산한다.
변수 res는 현재까지 작업한 시간을 나타내고, result는 일을 제 시간에 끝낼 수 있는 가장 늦은 시간을 나타내는 변수이다.
정렬한 s 를 돌면서
현재까지 작업한 시간을 추가해주고
가장 끝낼 수 있는 늦은 시간을 업데이트 해줘야하는데.
limit-res는 현재 일을 끝내야 하는 시간에서 현재까지 작업한 시간(res)을 뺀 값으로, 현재 일을 제 시간에 끝낼 수 있는 시간입니다.
min(result, limit-res)는
현재 계산된 result와 limit-res 중에서 작은 값을 선택하여 result에 저장한다.
즉 result에는 현재까지의 일들 중 가장 늦게 일어날 수 있는 시간이 저장된다.
이해가 안 될 수도 있으니 예를 들어보겠다.
4
17 63
32 95
38 129
11 104
정렬 >>
[[17, 63], [32, 95], [11, 104], [38, 129]]
포문을 한 번 돌면
min(1e9,63 - 17) 으로 46 가 된다. 즉 46일때 일을 시작하면 일을 끝 마칠 수 있다는것이다.
2 번째 포문을 돌면 일을 17과 32 두개를 해야하고 그것은 95까지 끝내야한다.
그럼 95 -49 이므로 46이 나오고, 첫 번째 포문에서 나온 46과 비교하면 똑같으므로 46에서 시작하는 것이 베스트이다.
3 번째 포문을 돌면
17,32,11 3가지 일을 다 해야하면서 104 안에 끝내야한다. 그럼 60 이 된다.
근데 위에 처럼 46 시작하면 첫 번째(46+17)와 두 번째(63+32)는 일을 끝낼 수 가 있지만, 세 번째 일은 끝낼 수 없다(95+11 > 104)
숫자 2가 더 크기 때문에 할 수 없다. 그렇기 때문에 min(46과, 3가지일 다 끝내야 하는 수 (104) 에서 총 일 (60) 빼기) 을 비교한 값인 44 가 나오게 된다.
댓글