내일 여행간다. 고기 구워먹을 예정인데 난 정말 고기를 탐낼 것이다.
그래서 탐욕법(그리디) 문제를 풀이해볼까 싶다. 응..?
ㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋㅋ

BOJ 1202 - 보석 도둑 링크
(2022.08.19 기준 G2)
(치팅이고 뭐고 배고프다 우씌! 그래도 치팅하지 말아요)

문제

각 무게 M, 가치 V인 보석 N개가 있고, 각 최대 무게 C의 보석 하나만 담을 수 있는 가방 K개가 있을 때
담을 수 있는 보석의 최대 가치합

알고리즘

DP를 이용한 냅색(배낭 문제)가 먼저 떠오른다. 하지만 가방 하나에 보석 하나만 담을 수 있기 때문에 이분 매칭 느낌으로 매칭 시켜줘야 한다. (이분 매칭도 될 것 같은데 아마 N과 K의 범위 때문에 시간 초과가 날 것이다)
그래서 무게, 가치를 정렬하여 '그리디'하게 풀었다.

풀이

보석을 무게가 오름차순이 되게 정렬하고 가방도 오름차순이 되게 정렬한다.
그 다음, 정렬된 가방 차례대로 넣을 수 있는 보석을 전부 뽑아서 가치가 내림차순이 되게 정렬한 뒤, 지금까지 뽑은 보석이 남아 있다면 하나씩 뽑아주면 된다.
참 쉽죠..?
그냥 한 테스트케이스로 그림을 그려가며 설명해보겠다.

4 2
5 110
7 80
4 100
6 90
7
5

이 테스트케이스로 살펴보자.

먼저 보석과 가방을 테스트케이스대로 그려보면

이렇게 된다. 빨강은 무게, 파랑은 가치다. (도토리 같이 생긴게 가방이다..)
먼저 보석과 가방을 무게가 오름차순이 되게끔 정렬해보자.

정렬이 완료되면 위 그림처럼 될 것이다.

이제 가방이 정렬된 차례대로 살펴보자.
첫번째 가방은 버틸 수 있는 무게가 5다.
그러면 무게 5까지의 보석을 전부 담을 수 있을 것이다.
여기서 무게 5까지의 보석을 뽑아서 따로 가치가 내림차순이 되게 정렬해보자.
그림으로 그려보면

이렇게 된다.
그럼 여기서 가방 5에 무게 5, 가치 110인 보석을 담으면

위 그림처럼 된다.
아까 뽑았단 보석들은 그대로 놔둬야 한다.
왜냐하면, 가방들은 전부 무게 순으로 정렬했기 때문에 이미 뽑은 보석은 다음 가방에도 전부 넣을 수 있기 때문이다.
이게 핵심이다.

자 이제 다음 두번째 가방은 버틸 수 있는 무게가 7이다.
그러면 무게가 7까지의 보석을 전부 뽑아서 아까처럼 가치가 내림차순이 되게 정렬해보자.

위 그림처럼 되는데, 그러면 가방에 무게가 4, 가치가 100인 보석을 담으면 된다.
그리고 이제 더 이상 담을 가방이 없기 때문에 정답은 210이 된다.

이 방식을 코드로 구현하면 된다.

주의사항

주의사항까지는 아니고 내가 계속 맞왜틀했는데 왜냐하면..
아직 뽑지 않은 보석이 더 이상 없다고 루프문 끝내면 안된다.
이미 뽑았지만 가방에 담을 수 있는 보석이 남아 있을 수 있기 때문이다.

너무나 간단하지만 이걸로 너무 많이 틀렸음

코드

import sys; input = sys.stdin.readline
import heapq
from collections import deque

N, K = map(int, input().split())
J = deque(sorted(list(map(int, input().split())) for _ in range(N))) # 최소 힙을 써도 되고 그냥 정렬된 덱으로 써도 무방하다.
B = sorted(int(input()) for _ in range(K))
queue = [] # 담을 수 있는 보석들을 가치 내림차순으로 정렬하여 저장할 리스트
answer = 0
for b in B: # 가방이 정렬된 차례대로 살펴본다
    while J and J[0][0] <= b: # 아직 뽑지 않은 보석이 남아 있고 그 중 최소 무게인 보석이 가방에 담긴다면
        M, V = J.popleft() # 그 보석을 뽑아서
        heapq.heappush(queue, -V) # 최대 힙 방식으로 queue에 담아준다.
        # 이 과정을 될 때까지 반복
    if queue:
        answer -= heapq.heappop(queue) # 가능한 보석이 있다면 하나를 뽑아서 가방에 담는다
print(answer)

여담

그리디는 간단하지만 파고들수록 어렵다. 이 문제도 코드만 보면 간단하게 보이겠지만, 어떻게 하면 풀릴지 그 방법을 떠올리는 과정이 정말 어렵다.

나 이제부터 휴가다. (다음주 주말까지 쭉!) 휴가 시즌동안 잠깐 코딩을 내려놓을 생각이다. 코딩하랴 일하랴 로아하랴 못했던 일상 블로그나 멜론 DJ에 신경 써볼 생각이다. 그때까지 안뇽~