[백준/Python] 1263번 - 시간 관리

문제

백준 1263번 - 시간 관리

해결 과정

• 주어진 문제의 조건에서 "가장 늦게 일을 시작할 수 있는"에 초점을 맞추기
• 끝내야할 시간이 가장 늦은 순으로 정렬
• ans 끝내야할 시간이 가장 늦은 일의 시작 시간
• 시작해야하는 시간만을 비교한다.
  • i 번째 일을 끝내야할 시간보다 현재 시간이 크다면
    • ans는 i번째 일이 걸리는 시간
  • i 번째 일을 끝내야할 시간보다 현재 시간이 작다면
    • ans는 ans - i번째 일이 걸리는 시간

시행착오

• 문제 해석을 내 마음대로 하는 경향이 있다. (아주 큰 문제,,)
  • 만약 0시부터 시작하여도 일을 끝마칠 수 없다면 -1을 출력한다.
  • 24시 안에 끝내지 못한다면이라고 해석했다..............쯧
  • 그 뜻이 아니라 마지막 할 일이 해당 시간(Si)내에 끝내지 못한다면!
• 시간 초과.. 왜지?

import sys
n = int(sys.stdin.readline())
time = []

for _ in range(n):
  time.append(list(map(int,sys.stdin.readline().split())))

time.sort(key = lambda x: x[1])

start = time[0][1] - time[0][0]
idx = 0
while True:
  now = start
  idx = 0
  for i in range(n):
    now += time[i][0]
    idx += 1
    if now > time[i][1]:
      start -= 1
      break
  
  if now > time[n-1][1]:
    if start < 0:
      print(-1)
      break
    else:
      start -= 1
  
  if idx+1 == n:
    print(start)
    break

• 탐욕법이므로, "주어진 문제의 조건인 가장 늦게 일을 시작할 수 있는"에 초점을 맞춰서 풀기

풀이

import sys
n = int(sys.stdin.readline())
time = []

for _ in range(n):
  time.append(list(map(int,sys.stdin.readline().split())))

# [[5, 20], [1, 16], [8, 14], [3, 5]]
time.sort(key = lambda x: x[1], reverse = True)

# 가장 늦은 시간에 해도 되는 일이 최소 시작해야하는 시간
ans = time[0][1] - time[0][0]

# 시작해야하는 시간만을 비교
for i in range(1,n):
  if ans > time[i][1]:
    ans = time[i][1] - time[i][0]
  else:
    ans -= time[i][0]

print(ans) if ans >= 0 else print(-1)