1202번 보석 도둑
코딩테스트 : 1202번 보석 도둑
| 1 초 | 256 MB | 89479 | 22219 | 15308 | 22.951% |
문제
세계적인 도둑 상덕이는 보석점을 털기로 결심했다.
상덕이가 털 보석점에는 보석이 총 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)
모든 숫자는 양의 정수이다.
출력
첫째 줄에 상덕이가 훔칠 수 있는 보석 가격의 합의 최댓값을 출력한다.
사고의 흐름은 다음과 같았다.
우리가 목표하는 바 : 보석 가격의 합이 최댓값을 구하는 것
주어진 정보 : 총 보석 수 , 각 보석의 무게와 가격, 총 배낭 수, 총 배낭의 무게
처음에는 가방에 넣을 수 있는 보석들 중, 가장 가치가 높은 보석들을 순서대로 가방에 넣으면 되지 않을까 하고 생각했다.
다만 이렇게 된다면 '특정 가방만 들 수 있는 보석'을 챙기지 않게 되는 문제가 있다.
예를 들어, 10의 무게를 들 수 있는 가방이 있고 , 가치가 9 / 무게가 10인 보석과 가치가 10이고 무게가 9인 보석이 있다고 하자.
단순하게 보면 가치가 10인 보석을 선택하는 것이 맞겠지만 , 나머지 가방의 무게들 중 10을 들 수 있는 가방이 없고, 다른 보석들의 가치가 9보다 많이 낮다면 가치가 9인 보석을 가방에 넣고, 나머지 가방으로 가치가 10인 보석을 드는 것이 올바른 답이다.
따라서, 기준이 가방이 아닌 보석의 가치가 되어야 한다고 생각했다.
보석을 '가치가 높은 순서대로' 정렬하고, 하나씩 보석을 꺼내면서 무게를 본 후, 그 무게를 들 수 있는 가방 중 가장 가벼운 무게를 들 수 있는 가방을 선택하는 방법을 생각했다. 그래서 다음과 같은 코드가 나왔다.
public class BackJoon
{
public static void Main()
{
// Idea : 보석은 가치 순으로 , 가방은 무게 순으로 정렬
// 보석을 하나씩 꺼내면서 그 무게를 담을 수 있는 가장 적은 무게의 가방을 픽한다.
// 보석 N / 가방 수 K
int[] NK = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
int N = NK[0];
int K = NK[1];
// 만약 튜플을 쓰지 않는다면 어쩌지 ?
// List<(int, int)> jewelPrice = new List<(int, int)>()
// 첫 번째 인덱스는 무게, 두 번째 (우선순위)는 가치
PriorityQueue<(int weight, int value), int> weightPrice = new PriorityQueue<(int weight, int value), int>();
for (int i = 0; i < N; i++)
{
int[] input = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
int weight = input[0];
int value = input[1];
// 가치가 높은 순서대로 해야하니 -
weightPrice.Enqueue((weight, value), -value);
}
int[] bagWeight = new int[K];
for (int i = 0; i < K; i++)
{
int temp = int.Parse(Console.ReadLine());
bagWeight[i] = temp;
}
Array.Sort(bagWeight);
// 보석 하나 당 가치가 1억이 넘을 수 있으므로 ,21억이 넘어도 저장될 수 있게
long totalValue = 0;
bool[] UsedBag = new bool[K];
int bagCount = 0;
// 종료 조건 : 보석이 다 Dequeue되거나, 가방이 사라지면
while (weightPrice.Count > 0 && bagCount < K)
{
(int weight, int value) = weightPrice.Dequeue();
for (int i = 0; i < K; i++)
{
if (!UsedBag[i] && bagWeight[i] >= weight)
{
totalValue += value;
UsedBag[i] = true;
break;
}
}
}
Console.WriteLine(totalValue);
}
}
문제는 매 보석마다 모든 가방을 순회하므로 시간복잡도가 N^2이라는 것이다.
왜 이렇게 했냐면 '무게와 가치는 비하지 않기 때문에' 쓴 가방에서 인덱스를 증가시키는 방법으로는 올바르지 않은 답이 나올 수 있다.
public class BackJoon
{
public static void Main()
{
// Idea : 보석은 가치 순으로 , 가방은 무게 순으로 정렬
// 보석을 하나씩 꺼내면서 그 무게를 담을 수 있는 가장 적은 무게의 가방을 픽한다.
//Idea2 : 무게 순으로 둘 다 정렬한뒤 , 하나씩 올려가면서 가능한 가치의 보석들을
// 우선순위 큐에 저장하고, 하나씩 꺼내면서 쓴다.
// 보석 N / 가방 수 K
int[] NK = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
int N = NK[0];
int K = NK[1];
// 만약 튜플을 쓰지 않는다면 어쩌지 ?
// List<(int, int)> jewelPrice = new List<(int, int)>()
List<(int, int)> list = new List<(int, int)>();
for (int i = 0; i < N; i++)
{
int[] MV = Console.ReadLine().Split(' ').Select(int.Parse).ToArray();
int weight = MV[0];
int value = MV[1];
list.Add((weight, value));
}
list.Sort();
List<int> bagWeight = new List<int>();
for (int i = 0; i < K; i++)
{
int tempWeight = int.Parse(Console.ReadLine());
bagWeight.Add(tempWeight);
}
bagWeight.Sort();
// 둘 다 넣고 무게순으로 정렬했다
// 이제 가방을 보면서 가능한 무게를 다 보고, 거기서 가장 높은 가치를 지닌 물품을 선택하면 된다.
PriorityQueue<int, int> ValuePriorityQueue = new PriorityQueue<int, int>();
int listCount = 0;
long totalValue = 0;
foreach (int weight in bagWeight)
{
//ValuePriorityQueue.Clear();
// 리스트의 count번째 인덱스가 존재하고, 그 인덱스의 무게 (무게순으로 정렬했으니까)가
// 현재 무게보다 작거나 같을 때 (담을 수 있을 때)
while (listCount < N && list[listCount].Item1 <= weight)
{
// 중요 : - 붙이기
ValuePriorityQueue.Enqueue(list[listCount].Item2, -list[listCount].Item2);
listCount++;
}
if (ValuePriorityQueue.Count > 0)
{
totalValue += ValuePriorityQueue.Dequeue();
}
}
Console.WriteLine(totalValue);
}
}
1. -를 잘 붙여야 한다, 우선순위 큐 라이브러리를 처음 써 보다 보니까 생각보다 힘들다.. ㅎ
2. 위 코드에서는 ValuePriorityQUeue를 초기화 시켜주는 코드가 남아 있는데 초기화 해 줄 필요가 없다. 왜 ? '가능한 무게'들은 계속 남아있으니까 !!!
3. 따라서 가방을 무게 기준으로 오름차순 정렬한 후, 작은 무게 가방부터 처리해야 한다. 그래야 무게 제한이 커지는 과정에서, 이전에 담을 수 있었던 보석들을 그대로 활용할 수 있고, 우선순위 큐에는 항상 현재까지 담을 수 있는 보석이 모두 들어 있게 된다.
결국 한참을 고민하다 정렬 기준을 다르게 해야 한다는 생각이 들었다.
가치로 정렬하면 각 보석의 무게가 제각각이어서, 가방 리스트를 일관되게 탐색할 수 없다. 그 결과 보석마다 모든 가방을 다시 순회해야 하고, 시간 복잡도가 비효율적으로 커지게 된다. 그렇기 때문에 같은 기준으로 정렬할 수 있는 '무게'를 기준으로 정렬하고 문제를 풀어야 한다고 생각했다.
우리는 인덱스 (보석의 인덱스)를 증가시키면서 문제를 풀 것이기 때문에 오름차순으로 정렬되어 있어야 한다. 그래야 다음 무게의 가방으로 넘어 갔을 때, 그 전까지의 가능한 가치 리스트를 똑같이 쓸 수 있고, 이게 올바른 답을 찾는 길이기 때문이다.
가능한 가치 리스트들은 항상 정렬되어 있고, 가장 큰 값이 0번째 인덱스에 있어야 하기 때문에 여기서 우선순위 큐를 사용했다.
다른 사람의 흥미로운 풀이
다른 사람 풀이(440줄짜리)를 확인해 보았다.
풀이 방식은 동일했지만, 언어적 특성(주석 없음, 간결한 문법) 때문에 코드가 매우 짧아 보였다.
우선순위 큐 문제가 끝났다.
- 문제를 마주쳤을 때 '최대/최소를 자주 뽑으면서 해결하는 문제'라면 우선순위 큐를 고려해야 한다.
- 위 문제처럼 여러가지 데이터가 섞여 있을 때는, 공통된 데이터 (여기서는 무게)를 기준으로 정렬하는 것을 기본으로 생각한다.
우선은 이 두 가지 생각을 머릿속에 넣고 있으면서 문제를 풀어야겠다.