[Gold II] 보석 도둑 - 1202

문제 링크

성능 요약

메모리: 107892 KB, 시간: 1396 ms

분류

자료 구조, 그리디 알고리즘, 정렬, 우선순위 큐

문제 설명

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

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

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

입력

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

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

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

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

출력

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

---

문제 풀이

문제 분석

이 문제는 보석의 무게와 가격, 그리고 가방의 최대 무게 제한이 주어졌을 때, 가방에 담을 수 있는 보석 가격의 합의 최댓값을 구하는 문제입니다. 각 가방에는 하나의 보석만 담을 수 있습니다.

접근 방법

이 문제는 그리디 알고리즘과 우선순위 큐(heapq)를 사용하여 해결할 수 있습니다. 핵심 아이디어는 다음과 같습니다.

1. 가방을 오름차순으로 정렬: 무게 제한이 작은 가방부터 고려합니다.
2. 보석을 무게가 작은 순서대로 정렬: 가방에 넣을 수 있는 보석을 쉽게 찾기 위함입니다. (코드에서는 보석을 가격이 높은 순서로 정렬해놓고, while문에서 pop()을 사용해 무게가 작은 순서대로 접근하고 있습니다.)
3. 가방마다 넣을 수 있는 보석 중 가장 비싼 보석을 선택: 힙(우선순위 큐)을 사용하여 가방에 넣을 수 있는 보석들의 가격을 관리하고, 가장 높은 가격의 보석을 선택합니다.

구현 설명

1. 입력 및 초기화

• n, k = map(int, input().split()): 보석의 개수 N과 가방의 개수 K를 입력받습니다.
• jewels = []: 보석 정보를 저장할 리스트를 초기화합니다.
• bags = []: 가방 정보를 저장할 리스트를 초기화합니다.
• for i in range(n): jewels.append(list(map(int, input().split()))): 보석의 무게와 가격을 입력받아 jewels 리스트에 저장합니다.
• for i in range(k): bags.append(int(input())): 가방의 최대 무게를 입력받아 bags 리스트에 저장합니다.

2. 정렬

• jewels.sort(reverse=True): 보석을 가격이 높은 순서대로 정렬합니다. (무게가 작은 순서로 정렬하고 가방에 담을 수 있는지 확인하는 방식도 가능)
• bags.sort(): 가방을 무게 제한이 작은 순서대로 정렬합니다.

3. 가방에 보석 담기

• can_take = []: 현재 가방에 넣을 수 있는 보석들의 가격을 저장하는 최소 힙(min heap)입니다. (파이썬의 heapq는 최소 힙을 제공하므로, 가격에 음수를 취해 최대 힙처럼 사용합니다.)
• answer = 0: 훔칠 수 있는 보석 가격의 합을 저장할 변수를 초기화합니다.
• for bag in bags:: 각 가방에 대해 반복합니다.
• while jewels:: 아직 확인하지 않은 보석이 있는 동안 반복합니다.
• if jewels[-1][0] <= bag:: 현재 보석의 무게가 가방의 최대 무게보다 작거나 같으면 (가방에 넣을 수 있으면)
• weight, value = jewels.pop(): 보석 리스트에서 해당 보석을 꺼내고 무게와 가격을 저장합니다.
• heapq.heappush(can_take, -value): 보석의 가격에 음수를 취하여 can_take 힙에 넣습니다.
• else: break: 현재 보석의 무게가 가방의 최대 무게보다 크면, 더 이상 현재 가방에 넣을 수 있는 보석이 없으므로 내부 while 루프를 종료합니다.
• if can_take:: 현재 가방에 넣을 수 있는 보석이 하나 이상 있다면,
• answer -= heapq.heappop(can_take): can_take 힙에서 가장 작은 값(절댓값이 가장 큰 음수, 즉 가장 비싼 보석)을 꺼내어 answer에 더합니다.

4. 결과 출력

• print(answer): 훔칠 수 있는 보석 가격의 합의 최댓값을 출력합니다.

⏱복잡도 분석

• 시간 복잡도:

  • 보석 정렬: O(N log N)
  • 가방 정렬: O(K log K)
  • 가방에 보석을 담는 과정: O(N log N + K log N) (각 가방에 대해 최대 N개의 보석을 검사하고, 힙 연산은 log N)
  • 전체 시간 복잡도: O(N log N + K log K + N log N + K log N) = O((N+K)log(N+K)) (N과 K중 큰 값에 의해 좌우됨)

• 공간 복잡도:

  • jewels: O(N)
  • bags: O(K)
  • can_take: O(N) (최악의 경우 모든 보석이 힙에 들어갈 수 있음)
  • 전체 공간 복잡도: O(N + K)

핵심 포인트

1. 정렬 활용: 보석과 가방을 정렬하여 효율적인 탐색이 가능하게 합니다. 가방을 무게 제한이 작은 순서대로 처리하는 것이 중요합니다.
2. 우선순위 큐(힙) 활용: 각 가방에 넣을 수 있는 보석 중 가장 비싼 보석을 빠르게 찾기 위해 힙을 사용합니다.
3. 그리디 접근 방식: 각 가방마다 최적의 선택(가장 비싼 보석)을 함으로써 전체적인 최적해를 찾습니다.

풀이 코드

import sys
import heapq

input = sys.stdin.readline

n,k = map(int, input().split())

jewels = []

for i in range(n):
    jewels.append(list(map(int, input().split())))

bags= []
for i in range(k):
    bags.append(int(input()))

jewels.sort(reverse=True)
bags.sort()

can_take = []

answer = 0
for bag in bags:
    while jewels:
        if jewels[-1][0] <= bag:
            weight, value = jewels.pop()
            heapq.heappush(can_take, -value)
        else:
            break

    if can_take:
        answer -= heapq.heappop(can_take)

print(answer)