[백준] 1202 - 보석 도둑

1. 문제

1202번: 보석 도둑

2. 개요

보석들의 무게와 가치, 가방들의 최대 무게가 주어진다.

한 가방에는 보석 하나만 넣을 수 있다.

이 때 훔칠 수 있는 보석의 최대 가치를 구하는 문제.

3. 풀이 및 코드

3-1. 풀이

처음에 문제랑 입력을 대충 봤을때는 냅색 문제인가 했는데 아니었다.

먼저 입력받은 보석들과 가방들을 각각 무게, 최대무게의 오름차순으로 정렬한다.

이후 가벼운 가방 → 가벼운 보석순으로 탐색한다.

이때 보석의 무게가 가방보다 가볍다면 가방에 넣을 수 있는 보석이므로 따로 저장한다.

보석의 무게가 더 무겁다면 넣을 수 없는 보석이므로 해당 보석의 인덱스만 저장해둔다.

따로 빼놓은 보석들 중 가장 가치가 큰 보석을 가방에 담고, 다음 가방으로 넘어간다.

보석은 위에서 저장한 인덱스의 보석부터 다시 탐색한다.

가방의 최대무게는 계속 늘어날것이고, 가져갈 수 있는 보석은 이미 저장해둔 상태이기 때문.

위 작업을 반복하고 답을 출력한다.

3-2. Python

import sys
import heapq

N, K = map(int, sys.stdin.readline().split())

jewels = []
bags = []
ans = 0

for _ in range(N):
    m, v = map(int, sys.stdin.readline().split())
    jewels.append([m, v])

for _ in range(K):
    bags.append(int(sys.stdin.readline()))

jewels.sort()
bags.sort()

idx = 0
tmp = []
for bag in bags:
    while idx < N and bag >= jewels[idx][0]:
        heapq.heappush(tmp, jewels[idx][1] * -1)
        idx += 1

    if tmp:
        ans += heapq.heappop(tmp) * -1

print(ans)

3-3. C#

class Program
    {
        static void Main(string[] args)
        {
            int[] input = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
            long answer = 0;
            int N = input[0];
            int K = input[1];

            List<int[]> jewels = new List<int[]>();

            for (int i = 0; i < N; i++)
            {
                input = Array.ConvertAll(Console.ReadLine().Split(), int.Parse);
                jewels.Add(input);
            }

            jewels = jewels.OrderBy(x => x[0]).ToList();

            List<int> bags = new List<int>();

            for (int i = 0; i < K; i++)
            {
                bags.Add(Int32.Parse(Console.ReadLine()));
            }

            bags.Sort();
            PriorityQueue<int, int> priorityQueue = new PriorityQueue<int, int>();
            int idx = 0;
            foreach (int bag in bags)
            {
                while (idx < N && bag >= jewels[idx][0])
                {
                    priorityQueue.Enqueue(jewels[idx][1], jewels[idx][1] * -1);
                    idx++;
                }

                if (priorityQueue.Count > 0)
                    answer += priorityQueue.Dequeue();
                    
            }

            Console.WriteLine(answer);
        }
    }

Python에서는 heapq, heapq가 내장되어있지 않은 C#은 PriorityQueue를 활용했다.