DAMPER's blog

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 처음에 이 문제를 보고 바로 동전DP를 떠올렸지만, 각 가방에 한 개의 보석만 넣을 수 있고, 각각의 가방에 넣을 수 있는 보석의 무게가 다르기 때문에 조금 다른 문제라 생각했다. 풀이 방법 용량이 작은 가방부터 넣을 수 있는 최대 가치의 보석을 넣으면 된다. 예를들어, 아래와 같은 상황이라고 하자. 먼저 가방 용량을 오름차순으로 정렬하고, 보석을 무..