백준 코딩테스트/그리디(Greedy)

1202번: 보석 도둑 (2024 / 8 / 15) - 골드 2

monkeykim 2024. 10. 7. 00:13

문제

세계적인 도둑 상덕이는 보석점을 털기로 결심했다.

상덕이가 털 보석점에는 보석이 총 N개 있다. 각 보석은 무게 Mi와 가격 Vi를 가지고 있다. 상덕이는 가방을 K개 가지고 있고, 각 가방에 담을 수 있는 최대 무게는 Ci이다. 가방에는 최대 한 개의 보석만 넣을 수 있다.

상덕이가 훔칠 수 있는 보석의 최대 가격을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000)

다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000)

다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci ≤ 100,000,000)

모든 숫자는 양의 정수이다.

출력

첫째 줄에 상덕이가 훔칠 수 있는 보석 가격의 합의 최댓값을 출력한다.

 

예제 입력 1

2 1
5 10
100 100
11

예제 출력 1

10

예제 입력 2

3 2
1 65
5 23
2 99
10
2

예제 출력 2

164

 

코드

# N: 보석의 갯수
# M: 보석의 무게
# V: 보석의 가격
# K: 가방의 갯수
# C: 각 가방에 담을 수 있는 최대 무게
# 가방에는 최대 1개의 보석만 넣을 수 있음

import sys
import heapq as hq

# 보석의 갯수, 가방의 갯수 입력
n, k = map(int, input().split())

# 보석의 무게, 가격 튜플로 입력
jewel = [tuple(map(int, sys.stdin.readline().split())) for _ in range(n)]
jewel.sort()

# 각 가방이 들 수 있는 최대 무게 입력
bags = [int(sys.stdin.readline()) for _ in range(k)]
bags.sort()

# 최대 힙 초기화
heap = []
j = 0

count = 0

for bag in bags:  # 2, 10
    while j < n and bag >= jewel[j][0]:
        hq.heappush(heap, -jewel[j][1])
        j += 1

    if heap:
        count += -hq.heappop(heap)

print(count)

코드 풀이

  1. n, k를 입력받음
  2. 보석의 무게와 가격을 튜플을 요소로 가지는 리스트로 입력받음
  3. 가방이 들 수 있는 무게를 입력받음
  4. 최대 힙을 위한 heap 리스트 초기화
  5. 반복을 위한 j와 출력을 위한 count 초기화
  6. 가지고 있는 가방에 넣을 수 있는 보석을 넣기 위한 반복문 수행
    • 가장 작은 무게를 들 수 있는 가방부터 모든 보석들의 무게를 비교함
      • 모든 보석과 비교해야 하므로 while 반복문을 사용함
      • 가방보다 보석이 더 무겁다면 반복문을 탈출한다.
    • J의 역할
      • j는 0부터 시작하여 보석의 총 개수를 넘어가게 되면 멈추게 된다.
      • while 반복이 돌 때마다 j + 1씩 해주며 보석의 인덱스를 가리키는 역할을 한다.
      • 가방이 모든 보석의 무게보다 무겁다는 조건이 만족해도, j가 n보다 커지는 경우에는 while을 탈출하여 보석의 개수만큼만 반복문을 실행한다.
    • 최대힙 자료구조에는 가방이 들 수 있는 보석의 가치를 넣어준다.
      • 모든 가방은 그 가방이 들 수 있는 최대의 가치를 가진 보석을 가져가야 하므로 최대힙 자료 구조를 사용한다.
      • 가방에 대한 반복문이 끝날 때마다 최대힙에서 pop을 수행하여 count와 더해준다.
    • if의 역할
      • 가방이 들 수 있는 보석이 없는 경우. 즉, 모든 보석이 가방이 들 수 있는 무게보다 무거운 경우 heap에는 아무것도 담기지 않게된다.
      • 이럴 때 hq.heappop()를 사용하는 순간 index error가 발생하게 된다.
      • 따라서 heap에 요소가 있는지 체크해주어야 한다.

핵심 포인트

  1. 오름차순 정렬하기
    • 그리디 알고리즘에서는 정렬이 가장 중요하다.
    • 보석과 가방을 모두 오름차순으로 정렬해야 한다.
      • 반복문을 사용할 때, 가방은 그 가방이 들 수 있는 보석의 무게를 순차적으로 찾아야 하기 때문이다.
  2. 최대 힙 자료구조 사용하기
    • 각 가방은 그 가방이 들 수 있는 보석들 중 최대의 가치를 가지는 것을 담아야 하기 때문에 가장 큰 수를 루트 노드로 가지는 최대힙을 사용한다.
  3. 가방이 들 수 있는 무게를 최대 힙에 넣어주기
  4. 보석이 가방이 들 수 있는 무게보다 무거울 경우 처리하기
  5. 따라서 이후 가방이 while문을 돌더라도 이전 가방에서 비교한 보석과는 비교하지 않을 수 있다.