220524 - 보석 도둑

◾ 보석 도둑 : 백준 1202번

• https://www.acmicpc.net/problem/1202

문제

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

상덕이가 털 보석점에는 보석이 총 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)
• 모든 숫자는 양의 정수이다.

출력

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

입출력 예

Input	Output
2 1 5 10 100 100 11	10
3 2 1 65 5 23 2 99 10 2	164

---

◾ 풀이

1. 해설

• 이분 탐색을 활용한 방법(실패)
• 최대힙을 활용해 가방마다 가능한 최적의 보석 선택
  • 가방마다 가능한 보석을 최대힙에 추가
  • 루트에 있는 보석 선택(없는 경우 선택 X)

---

2. 프로그램

1. n, k, jewelries, bags 입력 및 정렬
2. 보석마다 남은 가방 중 최적의 가방 탐색
   • 이분 탐색을 활용해 가능한 가방 탐색
   • 작을 경우 큰 부분에서 다시 탐색
   • 클 경우 작은 부분에서 다시 탐색
   • 무게가 일치할 경우 종료
3. 가능한 가방을 찾았다면 추가

# 코드
# 이분 탐색을 활용한 방법
# 시간 초과 발생 : O(nlog(k))라 생각해 될 줄 알았는데..
import sys
input = sys.stdin.readline

n, k = map(int, input().strip().split(' '))
jewelries = [tuple(map(int, input().strip().split(' '))) for _ in range(n)]
bags = [int(input().strip()) for _ in range(k)]

bags.sort()                             # 가방 무게 순 오름차순
jewelries.sort(key=lambda x : -x[1])    # 보석 가치 순 내림차순
answer = 0
# 가치가 높은 보석부터 차례로 확인
for m, v in jewelries:
    # 모든 가방을 사용했다면 종료
    if k == 0:
        break
    # 왼쪽, 오른쪽, mid 인덱스 계산
    left = 0
    right = k-1
    mid = (left + right) // 2
    now = mid
    # left가 right 이하일 경우 반복
    while left <= right:
        # 보석의 무게가 현재 mid 가방의 무게보다 작을 경우
        if m < bags[mid]:
            # 가능한 가방 인덱스 설정
            now = mid
            # 작은 부분에서 재탐색
            right = mid - 1
        # 보석의 무게가 현재 mid 가방의 무게보다 클 경우
        elif m > bags[mid]:
            # 큰 부분에서 재탐색
            left = mid + 1
        # 무게가 동일할 경우 종료
        else:
            now = mid
            break
    # 보석의 무게가 가방 무게 이하일 경우
    # 가치 누적, 사용한 가방 삭제
    if m <= bags[now]:
        answer += v
        bags = bags[:now] + bags[now+1:]
        k -= 1
print(answer)

1. n, k, jewelries, bags 입력 및 정렬
   • jewelries : 보석 무게 순 내림차순
   • bags : 가방 무게 순 오름차순
2. jewel_heapq(최대힙), answer 초기화
3. 가방마다 가능한 보석 최대힙에 추가(보석 가치)
4. 최대힙에 값이 있는 경우 최대값 answer에 추가

# 코드
# 최대힙을 활용한 방법
import heapq
import sys
input = sys.stdin.readline

n, k = map(int, input().split(' '))
jewelries = [tuple(map(int, input().split(' '))) for _ in range(n)]
bags = [int(input()) for _ in range(k)]

jewelries.sort(key=lambda x : -x[0])    # 보석 무게 순 내림차순
bags.sort()                             # 가방 무게 순 오름차순

jewel_heapq = []
answer = 0
for w in bags:
    while jewelries and w >= jewelries[-1][0]:
        m, v = jewelries.pop()
        heapq.heappush(jewel_heapq, -v)
    if jewel_heapq:
        answer += -heapq.heappop(jewel_heapq)

print(answer)