[그리디] Greedy Algorithm / 폭탄 해체 작업

문제링크

https://www.codetree.ai/missions/8/problems/the-bomb-dismantling?&utm_source=clipboard&utm_medium=text

코드트리 | 코딩테스트 준비를 위한 알고리즘 정석

1. 핵심

• 핵심: 시간제한이 감소하는 순으로 보며 해당 시간에 선택할 수 있는 폭탄 중 점수가 가장 높은 폭탄을 선택하는 것이 최선이다!
• 예시
  • 시간제한이 가장 긴 것부터 선택했을 때 가장 최대 이익을 얻을 수 있다.
  • 만약 time 1 때 9를 선택하면 다른 폭탄 8과 2는 선택할 수 없기 때문에 이익이 작아진다.

시간	1	2	3	4	5	6
터질 수 있는 폭탄의 후보	9	9	9	9	9	9
''	8	8	8	8	8	8
''	7	7	7	7	7
''	6
''	2

• 따라서 우리는 가장 늦은 시간부터 앞으로 오면서 이익이 가장 큰 폭탄들을 시간마다 선택하면 된다.
• 문제는 time 6때 9를 선택하면 다음은 time 5때는 8을 선택해야한다.
  • 그러면 9를 뽑고 나서 8도 저장을 하고 time 5 때 8을 뽑을 수 있어야한다. 즉 각 타임당 점수의 후보들을 저장해놓고 가장 큰 것부터 가져와서 시간에 점수를 배분해야한다. 
• 가장 큰 값을 먼저 뽑도록 만들기 위해서 max heap를 사용한다.

2. 코드(Python)

from heapq import heappush, heappop

t = int(input())
bombs = [list(map(int, input().split())) for _ in range(t)]
bombs.sort(key= lambda x: (x[1], x[0]))
MAX_TIME = bombs[-1][-1]

bomb_list = [[] for _ in range(MAX_TIME + 1)]
for score, limit in bombs:
    bomb_list[limit].append(score)

heap = []
cnt = 0
for time in range(MAX_TIME, 0, -1):
    for score in bomb_list[time]:
        heappush(heap, -score)
    if len(heap) == 0:
        continue
    q = -heappop(heap)
    cnt += q
    
print(cnt)