[Python] 7983. 내일 할거야(골5) / 그리디-정렬

목차

1. 문제

2. 핵심 아이디어

3. 코드

4. 배운 점

---

 

1. 문제

 

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

 

---

2. 핵심 아이디어

 

요약

- 끝나는 일자를 기준으로 내림차순 정렬합니다.

- 이전 과제 시작일은 시스템 최대값으로 초기화합니다.

- 이전 과제 시작일보다 현 과제 마감일이 더 이르다면 현 마감일자를 기준으로 시작일자를 초기화합니다.

- 이전 과제 시작일이 현 과제 마감일보다 같거나 더 이르다면 이전 과제 시작일 전날을 기준으로 시작일자를 초기화합니다.

 

예시)

3

걸리는 시간	마감일자
2	8
1	13
3	10

 

 

우선 마감일자를 기준으로 내림차순 정렬합니다.

 

걸리는 시간	마감일자
1	13
3	10
2	8

 

 

 

우선 가장 이른 시작일자 구할 것이기 때문에 시작일자를 최대값으로 초기화합니다.

start= sys.maxsize

 

이제 마감일자가 넉넉한 일자부터 차례대로 시작일자를 초기화합니다.

 

1) 13일 - 걸리는 시간 1일

 

이전 과제의 시작일(초기화된 시작일은) 시스템 최대값입니다.

현 과제의 마감일은 13일입니다.

 

더 적은 일자인 현 과제 마감일인 13을 기준으로 시작날짜를 초기화합니다.

 

과제 시작일은 

start= 13 - 1 + 1 => 13일로 초기화됩니다.

 

2) 10일 마감- 걸리는 시간 3일

 

이전 과제의 시작일은 13일입니다.

이번 과제의 마감일은 10일입니다.

 

그러므로 더 적은 일자인 현 과제 마감일을 기준으로 시작날짜를 초기화합니다.

 

이번 과제는 최소 8일에는 시작해야 합니다.

 

따라서 과제 시작일은

start = 10 - 3 +1 => 8일로 초기화됩니다.

 

3) 8일 마감 - 걸리는 시간 2일

 

이전 과제의 시작일은 8일입니다.

이번 과제의 마감일은 8일입니다.

 

이미 이전 과제가 8일에 시작되었으므로

이번에는 이전 과제의 시작일인 8일보다 하루적은 7일을 기준으로 시작날짜를 초기화합니다.

 

이번 과제는 최소 6일에는 시작해야 합니다.

 

start= 7-2+1  => 6일로 초기화됩니다.

 

이렇듯 마감날짜가 넉넉한 순으로

이전 과제 시작일이 더 이르냐, 

이번 과제 마감일이 더 이르냐를

기준으로 시작날짜를 초기화해줍니다.

 

 

---

한 가지 간단한 예시를 더 들어보겠습니다.

 

3

2 13

3 5

3 6

 

다음 입력값이 있다고 가정해봅시다.

 

먼저 똑같이 마감일을 기준으로 내림차순 해줍니다.

 

13 2

6 3

5 3

 

이제 각각 시작일자를 초기화해줍시다.

 

start= sys.maxsize

 

1) 13일 마감 -  2일 걸림

 

이전 과제의 시작일은 시스템 최대값입니다.

현 과제 마감일은 13일입니다.

 

더 이른 날짜인 13일을 기준으로 시작날짜를 초기화합니다.

 

start= 13 - 2 +1 => 최소 12일에 시작해야 합니다.

 

2) 6일 마감 -  3일 걸림

 

이전 과제 시작일은 12일입니다.

현 과제 마감일은 6일입니다.

 

더 이른 날짜인 6일을 기준으로 시작날짜를 초기화합니다.

 

start= 6 - 3 +1 => 최소 4일에 시작해야 합니다.

 

3) 5일마감 - 3일 걸림

 

이전 과제 시작일은 4일입니다.

현 과제 마감일은 5일입니다.

 

더 이른 날짜인  이전 과제를 시작하는 날(4일)의 전날인 3일을 기준으로 초기화합니다.

 

start= 3-3+1 => 최소 1일에 시작해야 합니다.

 

따라서 노는 날은 1-0으로 0일을 놀 수 있습니다.

 

---

3. 코드

import sys
import heapq

n= int(input())
q=[]

for _ in range(n):
  #d일이 걸리고 t일 안에 끝내야 함
  d,t = map(int, input().split())
  heapq.heappush(q, (-t, d))

start=sys.maxsize

while(q):
  end, duration = heapq.heappop(q)
  #print(end, duration)
  end=-end
  
  if start>end:
    start= end-duration+1
  else:
    start= start-duration
  #print(end, duration, start)

print(start-1)

---

4. 배운 점

- heapq를 통해 내림차순 정렬을 해주긴 하였지만 크게 효율에 상관은 없는 듯 하다.

- 정렬 문제의 주요 포인트 : 어떤 것이 우선적이어야 하는가

- 그리디 문제의 주요 포인트 : 단위 상황에서의 최선책이 전체 상황의 최선책을 보장하는가

 

=> 그리디+ 정렬 문제의 주요 포인트

: 어떤 순서로 고려해야 + 단위 상황에서의 최선책이 전체 상황의 해결책으로 이어지는가

 

---

유사한 문제

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