문제는 다음과 같다.
https://www.acmicpc.net/problem/1202
문제를 잘 읽고 풀이를 보도록 하자..
그리고, 주석을 집중해서 읽어보도록 하자
풀이는 다음과 같다.
import java.io.*;
import java.util.*;
public class Main {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
//보석을 arraylist로 입력받은 후 무게 순서대로 오름차순 정렬한다.
//가방에 담을 수 있는 최대 무게를 입력 받은 후 오름차순 정렬한다.
//가격 순서대로 내림차순 정렬을 하는 우선순위 큐를 생성한다.
StringTokenizer st1 = new StringTokenizer(br.readLine());
int N = Integer.parseInt(st1.nextToken());
int K = Integer.parseInt(st1.nextToken());
ArrayList<Jewel> list = new ArrayList<>();
for(int i = 0 ; i < N ; i++) {
StringTokenizer st2 = new StringTokenizer(br.readLine());
int w = Integer.parseInt(st2.nextToken());
int v = Integer.parseInt(st2.nextToken());
list.add(new Jewel(w, v));
}
Collections.sort(list, (o1, o2) -> o1.w - o2.w); //무게 오름차순
int[] bags = new int[K];
for(int i = 0 ; i < K ; i++) {
bags[i] = Integer.parseInt(br.readLine());
}
Arrays.sort(bags); //가방 용량순 오름차순
PriorityQueue<Jewel> pq = new PriorityQueue<>((o1, o2) -> o2.v - o1.v); //가격 내림차순
long answer = 0;
int index = 0;
//bags 가방용량오름차순, list 보석무게오름차순,
//pq 보석가격 내림차순 (우선순위 큐는 내림차순 해야 가장 큰값이 먼저 뽑힘.)
//현재 가방(bags[i])이 담을 수 있는 무게보다
//작거나 같은 무게를 가진 보석을 모두(아래의 while 문) 우선순위 큐에 담아준다.
//우선순위 큐의 제일 첫 번째 값(가장 가격이 비싼 보석)을
//꺼내어 더해준다.(아래의 if문)
//해당 내용을 가방 용량이 작은 순서부터 체크해준다.
for(int i = 0 ; i < K ; i++) { //가방 용량 작은것부터 봐가며 담을 수 있는 보석 다 담아주기
while(index < N && list.get(index).w <= bags[i]) {
Jewel curJewel = list.get(index);
pq.add(new Jewel(curJewel.w, curJewel.v));
index++;
}
//생각해보자. 만약 가방 무게 8, 9 용량이 있고 보석이 무게4 가격5 라면
//해당 보석은 가방 무게 8, 9에 둘 다 담을 수 있긴 하다.
//근데 해당 로직에서는,
//가방용량 8일때 해당 보석(무게4, 가격5)을 넣어주고, index++이 되기 때문에
//가방용량 9일때는 해당 보석을 패스하고 넘어간다.
//가방 용량을 작은 순서대로 하나하나 잡아가며 넣을 수 있는 보석들을 보고,
//그 넣을 수 있는 보석들 중에서 가장 비싼 친구를 넣는것이다.
//그런데, 이런 경우도 생각해 보자.
//8, 9 용량의 가방과 보석 a, b, c가 있다. (가격 a > b > c)
//8의 용량에 들어갈 수 있는 보석은 a, b 이다.
//그럼 a, b가 우선순위 큐에 들어가고, (pq.add(new Jewel(curJewel.w, curJewel.v));)
//우선순위 큐에서는 가격순으로 뽑혀 가방에 들어가기 때문에
//8번 가방에서는 a가 들어가게 된다. (가격 a > b이므로) (answer += pq.poll().v;)
//그 후에는 우선순위 큐에는 보석 b가 남게 된다.
//이후엔 9 용량의 차례에서 보석 c 가 우선순위 큐에 들어가도,
//어차피 우선순위 큐에는 보석 b가 남아있고 가격은 b > c 이므로
//9 용량의 가방에는 보석 b가 들어가게 된다
//자, 다 왔다.. 조금만 더 힘내서 위를 토대로 이제 정리해보자.
//큰 용량의 가방은
//더 작은 용량의 가방에 넣을 수 있는 보석을 전부 넣을 수 있다.
//그렇다면!
//작은 가방보다 큰 가방이 넣을 수 있는 보석의 선택지가 더 넓게 된다.
//그래서!
//작은 용량의 가방에 넣을 수 있는 보석들을 먼저 탐색하고,
//해당 보석들을 pq에 넣게 된다.
//bags[2] 까지 진행되었으면,
//bags[0], bags[1], bags[2] 들이 감당할 수 있는
//가장 비싼 보석들이 할당되고,
//pq에는 가방에 넣을 수 있었지만
//가격상 가방에 들어가지 못한 보석들이 대기하고 있는 것이다.
//그리고!
//해당 보석들은 앞으로는 계속해서 더 높은 용량의 가방이 나오므로,
//언제든지 가격만 가장 비싸다면 bags[i] 에 할당될 수 있다.
//이렇게 위의 두가지가 합쳐져 주석 위의 while문과 주석 아래의 if문에 의해
//가질 수 있는 보석의 최대 가치를 얻을 수 있게 된다.
if(!pq.isEmpty()) {
//지금 bag[i]의 용량까지 담을 수 있는 모든 보석이 pq에 담겨있다. 그중에 가장 비싼 하나만 뽑는것 (가방에 하나들어간대잖아)
answer += pq.poll().v;
}
}
bw.write(String.valueOf(answer));
bw.flush();
bw.close();
}
static class Jewel {
int w, v; //무게 weight, 값어치 value
public Jewel(int w, int v) {
this.w = w;
this.v = v;
}
}
}많이 어렵다. 진짜 어렵다.. 코드를 봐도 작동되는건 이해가 가는데,
왜 저렇게 작동시킬까? 가 이해가 안될 수도 있다.
아직 이해가 안갔으면, 아래를 한번만 더 읽어보자.
아래의 내용을 구현한 것이다,
큰 용량의 가방은
더 작은 용량의 가방에 넣을 수 있는 보석을 전부 넣을 수 있다.
(용량 8에 들어가는 보석은 당연히 용량 9의 가방에 들어간다.)
그렇다면!
작은 가방보다 큰 가방이 넣을 수 있는 보석의 선택지가 더 넓게 된다.
(용량 8인 가방보다 용량 9인 가방이 넣을 수 있는 보석이 더 많다.)
그래서!
작은 용량의 가방에 넣을 수 있는 보석들을 먼저
탐색하여 우선순위 큐(pq) 넣고,
해당 보석들을 pq에 넣게 된다. (여기까지가 while문)
그리고 현재 pq에 있는 보석중 가장 비싼 보석을 하나만 뽑아서 가방에 할당시켜 주는것이다. (여기까지가 if문)
for문의 i 가 2까지 진행되어
bags[2] 까지 진행되었으면,
bags[0], bags[1], bags[2] 들이 감당할 수 있는 무게의 모든 보석들이
pq에 들어간 후
가장 비싼 세개는
각각 bags[0], bags[1], bags[2]로 할당되었고,
pq에는 가방에 넣을 수 있었지만
가격상 다른 보석들에게 밀렸기에 가방에 들어가지 못한 보석들이 대기하고 있는 것이다.
그리고!
해당 pq에 대기하고 있는 보석들은 앞으로는 계속해서 더 높은 용량의 가방이 나오므로,
언제든지 가격만 가장 비싸다면 bags[i] 에 할당될 수 있다.
여담
처음에 풀때는, 무게에 비례한 보석 값.
즉 가성비를 따지면서 우선순위 큐로 풀어야 하나..?
그리고 주어진 시간상
정렬은 병합정렬(아래)를 사용해야 하나..?
하면서 많은 시간이 흘렀고,
아 이거 혼자 못풀겠구나.. 싶어서 남의 풀이를 참고해서 풀었다.
너무 아쉽지만,
다음에 비슷한 문제를 보면 꼭 맞췄으면 좋겠다....
static void mergeSort(int s, int e) {
if(s >= e) return;
int m = (s + e) / 2;
mergeSort(s, m);
mergeSort(m+1, e);
for(int i = s ; i <= e ; i++) {
tmp[i] = bags[i];
}
int l = s;
int r = m+1;
int k = s;
while(l != m+1 || r != e+1) {
if(tmp[l] > tmp[r]) {
bags[k] = tmp[r];
k++;
r++;
}
else {
bags[k] = tmp[l];
k++;
l++;
}
}
if(l != m) {
while(l != m) {
bags[k] = tmp[l];
k++;
l++;
}
}
if(r != e) {
while(r != e) {
bags[k] = tmp[r];
k++;
r++;
}
}
}
도둑질은 나빠요