[BOJ 6068🥇5] 시간 관리하기 (Python)

https://www.acmicpc.net/problem/6068

6068번: 시간 관리하기

문제

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

예제 입력 1 

4
3 5
8 14
5 20
1 16

예제 출력 1

2

 

⭕ CODE

n = int(input())

arr = []

for _ in range(n):
    t,s = map(int,input().split())

    arr.append((t,s))

# 끝나는 시간은 빠른순으로 오름차순
# 같은 끝나는 시간이라면 시간이 오래걸리는순으로 내림차순
arr.sort(key= lambda x: (x[1],-x[0]))

# 최소 결과를 위한 result
result = 1000001

# 지금까지의 시간을 알기위한 pre
pre = 0

for i in range(n):
	# arr[i][1] : 끝내야하는 시간
    # pre + arr[i][0] : 지금까지 사용한 시간 + 지금 일 걸리는 시간
    # 두개를 빼준 결과값이 0 이상이 되어야지 끝낼 수 있다.
    if arr[i][1] - (pre+arr[i][0]) >= 0:
    	# 지금까지 사용한 시간에 지금 일 걸리는 시간 더해주고
        pre += arr[i][0]
        # 결과값은 남은시간중에 작은것을 선택
        result = min(result,arr[i][1] -pre)
    # 불가능한 경우
    else:
        result = -1
        break
print(result)

✏️ Comment

sort(key = lambda)를 활용하여 일찍 끝나는 것을 기준으로 오름차순 시간이 오래 걸리는것을 기준으로 내림차순 하여서 문제를 풀면 해결가능한 문제였다.