백준7983(내일 할거야) - python 해결

내일 할거야

 

문제

아 과제 하기 싫다. 아무 것도 안 하고 싶다. 더 적극적이고 격렬하게 아무 것도 안 하고 싶다.

있잖아. 내가 아까 책상에다가 n개의 과제 목록을 적어놨어. 각각의 과제 i는 di 일이 걸리고, 오늘로부터 ti 일 안에 끝내야 해. 그러니까 오늘이 0일이면, ti일이 끝나기 전에 제출이야. 과제는 한번 시작하면 쉬지 않고 계속해야 해. 안 그러면 머리 아파 지거든.

근데 있잖아. 내가 지금 너무, 너무 아무 것도 안 하고 싶어. 그래서 오늘은 아무 것도 안 할 거야. 더 중요한 게 뭔지 알아? 사실 나 내일도, 모레도, 아무 것도 안 하고 싶어. 한 며칠 동안은 계속 아무 것도 안하려고. 아. 과제가 있을 때 내가 내일부터 연속으로 최대 며칠동안 놀 수 있는지 궁금하다. 궁금하긴 한데, 난 아무 것도 안 하고 싶어.

좋은 생각이 났다. 너희가 이걸 대신 구해주면, 내가 너희의 맞은 문제 수를 하나 올려줄게.

 

입력

첫째 줄에는 과제의 개수인 정수 n (1 ≤ n ≤ 106)이 주어진다.

이후 n개의 줄에 각각의 과제를 나타내는 두 정수 di, ti (1 ≤ di, ti ≤ 109)가 순서대로 주어진다. 오늘은 0일이다.

모든 입력에 대해, 오늘 아무 것도 안 해도 과제를 마무리 할 수 있는 방법이 존재함이 보장된다.

 

출력

내일(1일)부터 연속으로 최대 며칠 동안 놀 수 있는지를 출력한다. 가령, 답이 0이면, 내일 과제를 해야 하며, 1 이면, 모레에 과제를 해야 한다.

---

끝에서부터 일수를 줄이는 방법을 사용하였다.

그래서 정렬을 마감 날짜의 내림차순으로 정렬했다.

그래서 숙제해야하는 날만큼 줄이고 다음 숙제로 넘어가는 형식.

만약 현재까지의 날과 해당 숙제의 마감 날짜를 비교해서 작은거에서 해당 숙제의 수행 기간만큼 줄인다.

이런 방식으로 줄이면서 처음의 연속된 쉴 수 있는 날을 구한다.

 

'''
내일 할거야

'''
import sys
input = sys.stdin.readline

N = int(input())

# homeworks = [list(map(int,input().split())) for _ in range(N)]

# homeworks.sort(key=lambda x:-x[1])
# 숙제의 마감 날짜의 내림차순으로 정렬
homeworks = sorted([tuple(map(int, input().split())) for _ in range(N)], key=lambda x:-x[1])

# 시작 날짜는 마감 날짜가 가장 큰 것부터
idx = homeworks[0][1]
for d, t in homeworks:
    # 현재 날짜와 해당 숙제의 마감 날짜 중 작은 값
    idx = min(idx,t)
    # 숙제의 수행 기간 만큼 줄인다.
    idx -= d

print(idx)

주석 처리한 homeworks 보다 

현재 homeworks가 실행 속도가 빠르다. 

원래는 sort가 빠르다고 하는데 왜 이게 더 빠를까?