[백준/파이썬] 7983: 내일 할거야

문제 풀러 가기

문제가 참 재밌다..ㅋㅋㅋ
그리디로 풀었다.

1. 쭉~~ day 리스트에 튜플로 정보를 입력받았다. 이때 꼭 시작해야 하는 날(꼭 끝내야 하는 날 - 과제할 때 걸리는 일수 +1)을 구해서, (이날에는 꼭 시작해야 하는 날, 과제 할 때 걸리는 일수, 이때까지 꼭 끝내야 하는 날)형식의 튜플을 만들어서 리스트에 넣었다.
2. 리스트를 정렬하는데, 꼭 끝내야 하는 날 기준으로 내림차순으로 정렬했다. 오늘로부터 먼 순서대로 과제를 해야, 내일부터 가장 오랫동안 놀 수 있는 날을 구할 수 있으니까.
3. now는 과제를 시작하는 날을 의미한다. 일단 첫번째 과제를 시작하는 날은, 최대한 늦게 시작하는 게 좋으니까, 과제를 꼭 시작해야 하는 날로 초기화해서 시작한다.
4. 그 다음부터는 두번째 과제부터 마지막 과제까지 for문으로 본다. 만약에 과제를 꼭 시작해야 하는 날 시작해도 되면, 그때(must_start) 시작하게 한다. 그게 아니라 좀 더 일찍 시작해야 하면, 그때(now-need) 시작하게 한다.
   이 부분은 백준에서 주어진 예제를 보자.

   3
   2 8
   1 13
   3 10

   정렬하면 day 리스트는 [(13, 1, 13), (8, 3, 10), (7. 2. 8)]이 된다.
   그러면 첫번째 과제는 13일에 하루종일 한다. 그러면 now는 13이다.
   두번째 과제를 본다. 두번째 과제는 8일부터 시작하면 10일에 끝나서, 13일 전에 끝난다. (물론 9일이나 10일에 시작하고 싶기는 하겠지만, 마감 기한이 10일이니까 최대한 버티다가 과제를 한다. 그게 8, 9, 10일에 과제를 하는 것이다.) 그러면 now는 8이 된다.
   세번째 과제를 본다. 세번째 과제는 7일에 시작해서 8일에 끝내는 게 젤 늦게 하는 거라고 한다. 하지만!!!!! 두번째 과제를 8일에 하기 때문에, 세번째 과제는 7일에 시작하면 안되고 그것보다 일찍 시작해야만 한다. 그게 6일이다.(now-need= 8-2) 6, 7일에 과제를 하면 된다. 그러면 now가 6이다.

이제 모든 과제를 했다. now는 마지막 과제를 시작한 날!을 의미한다. 즉 그날도 과제를 한 날이다.
1일부터 과제를 안하고 최대로 놀 수 있는 날을 구하는 거니까 now-1을 하면 정답이 된다!!

import sys

input = sys.stdin.readline

n = int(input())
day = []
for i in range(n):
    a, b = map(int, input().split())
    day.append((b - a + 1, a, b))  # 이날에는 꼭 시작해야 하는 날, 과제 할 때 걸리는 일수, 이때까지는 꼭 끝내야 하는 날

day.sort(key=lambda x: (-x[2], -x[1])) # 꼭 끝내야 하는 일 기준으로 내림차순 정렬

now = day[0][0] # 첫번째 과제를 꼭 시작해야 하는 날

for i in range(1, n):
    must_start, need, must_finish = day[i]
    if now > (must_finish): # 최대한 버티다가 시작
        now = must_start
    else: # 최대한 버티다가 시작할 순 X. 좀 더 일찍 시작
        now = now - need

print(now - 1)