[Python] 1781. 컵라면(골2) / 우선순위 큐(heapq)

목차

1. 문제

2. 핵심 아이디어

3. 코드

4. 배운 점

---

 

1. 문제

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

1781번: 컵라면

---

2. 핵심 아이디어

 

2-1) heapq를 활용한 연산

 

여기서 만약 데드라인이라는 제한조건이 없어졌다면

우린 어떻게 문제를 풀었을까?

 

아마 컵라면을 많이 받는 순으로 문제를 풀었을 것이다.

 

여기에 데드라인이라는 제한조건이 생김으로써

어떤 문제를 선택한다는 것이 다른 문제를 포기한다는 것과 동치인 관계성이 생긴다.

 

그럼 이 관계성을 그리디적 사고로 어떻게 해결해야 할까?

 

이렇게 생각해보자

 

먼저 컵라면을 받는다.

그리고 내가 가진 컵라면이 최대가 되도록 데드라인을 맞춘다.

 

여기서 최대가 되도록 데드라인을 맞춘다는 의미는

다른 말로 데드라인을 넘을 때마다 가장 적은 컵라면 단위를 버린다는 것과 같다.

 

예를 들어보자

 

먼저 동호가 받는 컵라면 리스트를 만들어준다.

ramen= [ ] (아직 못받음)

 

만약 동호가 받는 컵라면을 데드라인과 받는 라면 수로 정렬하자

데드라인	받는 라면 수
1	6
1	7
2	4
2	5
3	1
3	2
6	1

 

이 상태에서 먼저 1,6을 고려하자.

 

먼저 컵라면 6을 받는다.

ramen= [6]

 

그리고 데드라인을 확인한다.

현재 ramen의 len 값은 1, 즉 1문제 풀었다.

그러므로 데드라인 1을 넘지 않는다.

 

계속 가보자

데드라인	받는 라면 수
1	7
2	4
2	5
3	1
3	2
6	1

이번엔 (1,7)이 들어온다.

 

먼저 컵라면을 받는다.

ramen= [6,7]

 

다음으로 데드라인을 넘는지 본다.분명 데드라인은 1일차 까지인데 동호는 문제를 2개(ramen의 len값) 풀고 라멘을 받았다.

 

여기서 동호는 라면을 하나 버려야 한다.최대값을 유지해야하므로 가장 작은 수인 6을 버린다.ramen=[7]

 

데드라인	받는 라면 수
2	4
2	5
3	1
3	2
6	1

 

이번엔 2,4

라면을 받는다.

ramen= [7,4]

 

데드라인 2를 넘지 않으므로 패스

 

데드라인	받는 라면 수
2	5
3	1
3	2
6	1

 

라면을 받는다.

ramen=[7,4,5]

 

데드라인 2를 넘는다. 가장 작은 4를 버리자.

ramen=[7,5]

 

데드라인	받는 라면 수
3	1
3	2
6	1

라면을 받는다.

ramen=[7,5,1]

 

데드라인 안넘으니까 ㄱㄱ

 

데드라인	받는 라면 수
3	2
6	1

 

맛좋은 라면을 받는다

ramen=[7,5,1,2]

 

데드라인 넘은 욕심쟁이 동호

가장 싼 하나를 버리자

ramen=[7,5,2]

 

이제 데드라인 3을 만족한다.

 

데드라인	받는 라면 수
6	1

라면을 받는다.

ramen=[7,5,2,1]

데드라인 6을 푼 문제수(len(ramen))이 넘지 않는다.

 

ㄱㄱ

 

그럼 동호가 받는 최대 라면은 [7,5,2,1]로 총 15개가 된다.

 

그럼 여기서 우선순위 큐는 언제 사용될까?

 

바로 가장 적은 단위를 버릴 때 사용된다.

데드라인을 넘을 때 동호는 최대의 라면 수를 유지하기 위해

가장 적은 단위를 버려야 한다.

 

이때 heapq.heappop을 통해 가장 적은 라면을 버리면 된다.

 

---

3. 코드

import sys
import heapq
input = lambda: sys.stdin.readline().strip('\n')

n= int(input())


problem=[]

for _ in range(n):
  problem.append(list(map(int, input().split())))

problem.sort() #문제 데드라인 순으로 정렬

result=[]

for d, ramen in problem:
  heapq.heappush(result, ramen) #우선 라면 받자
  if d <=len(result): #데드라인 넘었어? ->버려
    heapq.heappop(result)

print(sum(result))

---

4.배운 점

우선 순위 큐의 원리만 알았지 이것을 어떻게 활용할지에 대해 잘 감이 안잡히는 것 같다.

이 문제도 오래 고민하다 sort를 활용하였는데도 시간초과가 나서 결국 풀이를 보았던 것 같다.

 

뒤에 정리할 보석도둑 문제와 상당히 유사하기에 어떤 최대값 혹은 최소값으로 유지해야 하는 배낭문제 유형이 주어진다면 heapq를 활용한 풀이도 한번 고려해보자

 

비슷한 문제

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