알고리즘 (PS)/BOJ
[백준] 1202 - 보석도둑 (G2)
https://www.acmicpc.net/problem/1202 1202번: 보석 도둑 첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000) 다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000) 다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci www.acmicpc.net 자료구조를 사용하는 그리디 문제이다. 우선해야하는 조건이 2개가 엮여 있어서 난이도가 있는 문제였다. 나는 그리디 알고리즘 강의를 다시 복습해서 보고나서 아래와 같은 사고로 문제를 풀었다. 결국 그리디도 최적해를 구하는 알고리즘 중 하나인데, 이 문제에서 구해야하는 것은 '보석 가치 합의 최대'이다. 그렇다면 일단 보석의 가치만 놓고보면..
