[Python] 6068번 시간 관리하기 / 1263번 시간 관리 / 7983번 내일 할거야

 

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

6068번: 시간 관리하기

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

1263번: 시간 관리

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

7983번: 내일 할거야

---

 

23/08/27

 

 

보자마자 그리디 문제인 것을 파악할 수 있는 세 문제들로, 모두 같은 코드로 통과할 수 있기에 해설을 따로 적지 않고 합쳐서 적어보고자 한다. 

---

 

문제 접근 방식:

 

 

두 가지 정보가 주어진다. 하나는 일을 하는데에 걸리는 시간. 그리고 두번째는 각 일들의 마감 기한이 주어진다.

 

우리가 구하고자 하는 것은 주어진 일 모두를 마감 기한 내로 처리할 수 있는지의 여부와 만약 이것이 가능하다면 일을 시작하기 전까지 얼마 동안 "최대한" 일을 안 할 수 있는지에 대해서 구하는 것이다.

 

 

처음에 생각한 방법은 마감기한 순으로 정렬을 해보자는 것이었다.

 

주어진 일 모두를 마감 기한 내로 처리할 수 있는지의 여부를 따져야 되긴 하지만, 그건 둘째로 치고, "만약 일이 모두 가능하다면" 얼마동안 최대한으로 놀 수 있는가를 생각해 봤다.

 

이 상황에서 생각해 볼 수 있는 그리디적인 접근은 "가장 가까운 마감기한이 달린 일"을 살펴보는 것이다.

 

 

예를 들어, 마감기한이 $5, 14, 20, 16$순으로 주어져 있다면 당연히 마감 기한이 $5$인 일을 먼저 해야 함을 알 수 있다.

 

 

만약 마감기한이 동일한 일이 있다면 어떻게 일을 하던지 간에 상관없이 차례대로 마감기한의 역순으로부터 일을 쌓아나가며 하면 된다.

 

예를 들어, 마감 기한이 모두 $10, 10, 10, 10$으로 동일하지만 일하는 데 걸리는 시간이 $1, 2, 3, 3$이라면 어떻게 될까?

 

마감기한이 $10$이므로, 그전에 걸리는 시간이 $2$인 일을 하고, $3$인 일을 하고... 이런 식으로 쌓아나가며 구할 수 있을 것이다.

 

 

하지만, 가까운 마감기한이 달린 일을 살펴보는 방식에는 한계가 존재한다.

 

그 예시로, 마감 기한이 $10, 10, 11$이고 일하는 데 걸리는 시간이 $2, 3, 3$이라면, 우리는 그냥 $10$에서 $5$를 뺀 $5$만큼 놀 수 있을 것이라고 생각할 수 있겠지만, 실제로는 마감기한이 $11$인 일을 마감기한이 $10$인 일을 처리하고 나서 바로 처리할 수 없다.

 

때문에 마감 기한이 제일 가까운 일 "만" 살펴보면 오답이 생긴다.

 

 

그렇다면, 마감 기한을 전반적으로 살펴봐야 하는데 어떻게 해야 할까?

 

게다가 중요한 것은, 우리는 지금 일을 전부 처리하는 것이 가능하다는 전제 하에서 문제를 접근하고 있는데, 실제로는 이 또한 처리를 해줘야 하는 부분이다.

 

 

이전 예시에서 힌트를 얻어보자.

 

마감 기한이 $10, 10, 11$이고, 걸리는 시간이 $2, 3, 3$이라고 하자.

 

우리는 마감 기한이 $11$인 일을 마감기한이 $10$인 일을 처리하고 나서 바로 처리할 수 없다고 했다.

 

 

어쨌든 우리는 마감기한이 가장 긴 일을 최대한 뒤로 미루는 것이 유리하다는 것은 알고 있다.

 

그렇다면, 역으로 마감기한이 가장 긴 일을 중심으로 생각을 해보는 것이다.

 

마감기한이 가장 긴 일을 미룰 수 있을 만큼 미룬 다음에 마지막에 처리했다고 가정하자.

 

그러면, 마지막 일을 처리하기 직전이 새로운 마감기한이 될 것이다.

 

 

위의 예시라면, 당연히 마감기한이 $11$인 일이 마지막 일이 될 것이고, 이 일을 최대한 미룰 수 있을 만큼 미루는 것이 이득이다.

 

따라서 더 이상 미룰 수 없을 때는 시간이 $8$일 때가 될 것이다.

 

이후 $8$이 새로운 마감기한이 된다.

 

이 마감기한과 기존의 마감기한($10$)을 비교해 보면, 새로운 마감기한($8$)이 더 급박하다.

 

즉, 위에 제시한 접근 방법의 한계처럼, $10$에 맞춰서 일을 끝내면 안 되고 $8$까지 맞춰서 일을 끝내야 한다.

 

이후 $3$짜리 일을 했다고 하면 새로운 마감기한은 $5$가 되고, 마찬가지 방법으로 거꾸로 간다면 $3$이 된다.

 

즉, 이 예시에서의 답은 $3$이 된다.

 

 

이 규칙대로 구현하면 되는데, 새로운 마감기한과 기존 마감기한을 비교했을 때 더 작은 쪽이 새로운 마감 기한이 된다.

 

위의 예시에서는 새로운 마감기한($8$)이 더 작았기에 그게 그대로 마감기한이 되었지만, 그게 아닌 경우에는 더 작은 쪽이 새로운 마감 기한이 된다고 할 수 있다.

 

이렇게 하다가 만약 마감기한이 음수가 된다면 그건 일을 시간 내로 처리할 수 없다는 뜻이므로 $-1$을 출력하면 된다.

 

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더 보기를 누르면 확인할 수 있다.

# 6068번 시간 관리하기
# 그리디, 정렬
import sys
input = sys.stdin.readline
def main():
    N = int(input())
    li = [tuple(map(int, input().rstrip().split())) for _ in range(N)]
    li.sort(key=lambda tpl: tpl[1])
    time, end_t = li.pop()
    end_t -= time
    while li:
        time, end = li.pop()
        if end > end_t:
            end_t -= time
        else:
            end_t = end
            end_t -= time
        if end_t < 0:
            print(-1)
            return
    print(end_t)

main()