(Baekjoon) GreedyAlgorithm - (23) 보석 도둑

https://www.acmicpc.net/problem/1202

1202번: 보석 도둑

 

생각의 흐름 : 

 

 

우선 다음과 같은 가정을 해보고 문제를 풀이해본다.

 

보석의 가치를 최대한 높이려면 다음의 조건을 만족해야 된다라고 가정해본다.

1. 보석을 다 훔칠수도 못훔칠수도 있다.

2. 작은 가방까지 빈틈없이 활용해야 한다.

3. 보석의 가치가 높은것부터 넣는다.

 

변수 : 다음과 같은 배열을 생성한다.

{무게, 가치, 1당 가치}

로 정하고 1당가치로 배열을 오름차순으로 그다음에는 작은가방부터 오름차순으로 정렬한다.

순서 : 작은가방부터 채우기 시작하며

채울때는 오름차순으로 정렬되있는데로 삽입후 삭제한다

삭제하며 총액에 더하기를 한다.

작은 가방을 먼저 채운다.

-> 높은 가치가 있는것부터 넣고 그다음 큰가방을 채워넣는다.

반복 : 위의 과정을 남은 가방이 없거나 남은 무게에 들어갈 보석이 없을때까지 반복한다.

입력 : 가방의 무게와 보석의 입력할때마다 그 즉시 힙(heap)으로 정렬한다.(오름차순)

가장 가치가 높은것은 : 1당 가치는 높고 무게는 적게나가는것

 

 

그런데 이런식으로 넣을경우 다음과 같은 문제가 발생할수있다는걸 알게되었다.

 

10 200
9 198

의 선택지가 있을때 10의 공간을 가진 마지막 가방 한개에 10 200을 넣어야 9 198보다 2원정도 더 남길수있다.

하지만 내가 선택한 방식으로 할경우 1당 가치는 9 198이 10 200 보다 더 높기때문에 9 198을 넣어야 맞다.

하지만 정답은 아니다.

그렇기 때문에 1당 가치를 중심적으로 하는것은 옳지 않다.

 

다른기준이 필요하다. 10 200과 9 198의 결정적인 차이는 남은공간의 가치이다.

10 200 은 공간이 0 이 남지만

 9 198 은 공간이 1 이 남았다.

9 198은 남은공간 1을 매꿀만큼의 가치는 없는것이다. 그러니까 남은공간을 기준으로에 대한 가치가 필요하다.

 

1. 그러므로 내생각에 보석의 가치를 구할때 다음과 같이 따져야한다.

(가방의 무게/보석의무게) * 값어치를 계산해야한다.

그러니까 다음과 같이 가치가 정해질수있다.

-10이라는 공간의 가방에서는

(10/10) * 200 = 200

(10/9) * 198 = 198

이므로 10 200 의 가치가 더 높기때문에 10 200을 선택하는것이 맞다.

-5라는 공간의 가방에서는

(5/10) * 200 = 0

(5/9) * 198 = 0

이므로 전부 가치가 없기 때문에 제외된다.

 

그러므로 이런식으로 계산할경우 k라는 무게의 가방 n에 들어갈 가장 가치있는 보석을 구할수있다.

 

또 이런 경우를 따져볼경우 가장 가치있는 보석을 기준으로 먼저 집어넣을수는없다.

무게 10이라는 가방에 들어갈수있는 다음과 같은 보석이 있을때 그 가치다.

5 15 (30) 

4 15 (30) 
7 30 (30)

이런식일때는 가치가 동일하기 때문에 가장 보석의 무게가 낮은것이 더 가치가 높다고 할수있다.

2. 그러므로 가치가 동일하다면 보석의 무게가 낮은것이 더 가치가 높고 낮은것부터 넣는다.

 

그런데 문제를 잘못읽었다.

주어진 조건중에 다음과 같이 써있는것을 알수있다.

"가방에는 최대 한 개의 보석만 넣을 수 있다."

 

 

1. 주어진 보석을 무게를 기준으로 정렬한다. 그리고 가격을 기준으로 정렬한다.

2. 입력받은 가방을 오름차순으로 정렬한다.

3. 무게가 가장낮은것부터 계산하여서 가방에 들어가는 보석중 가장 가치있는것부터 가방에 집어넣는다.

4. 가방 무게가 낮은것부터 하는 이유는 높은것부터 할경우 가장 작은가방에 들어가도 될 보석을 큰가방에 집어넣음으로써 실패할수있기 때문이다.

 

 

 

 

package GreedyAlgorithm;

import java.util.Arrays;
import java.util.PriorityQueue;
import java.util.Queue;
import java.util.Scanner;

class Jewel_Info implements Comparable<Jewel_Info> {
    int Jewel_Info_Weight;
    int Jewel_Info_Price;

    public Jewel_Info(int Jewel_Info_Weight,int Jewel_Info_Price) {
        this.Jewel_Info_Weight = Jewel_Info_Weight;
        this.Jewel_Info_Price = Jewel_Info_Price;
    }
    
    public int compareTo(Jewel_Info ObjforCompare) {
        return this.Jewel_Info_Weight - ObjforCompare.Jewel_Info_Weight;
    }
}
public class _1202{

    public static void main(String args[]) {

        Scanner inputScanner = new Scanner(System.in);
        int Jeweler_had_Jewel = inputScanner.nextInt();
        int SangDuk_had_Bag = inputScanner.nextInt();
        Jewel_Info jewel_Info[] = new Jewel_Info[Jeweler_had_Jewel];
        int SangDuk_had_Bag_Info[] = new int[SangDuk_had_Bag];
        Queue<Integer> priorityQueue = new PriorityQueue<Integer>();

        for (int i = 0; i < Jeweler_had_Jewel; i++)
            jewel_Info[i] = new Jewel_Info(inputScanner.nextInt(), inputScanner.nextInt());
            
        for (int i = 0; i < SangDuk_had_Bag; i++)
            SangDuk_had_Bag_Info[i] = inputScanner.nextInt();
            
        Arrays.sort(jewel_Info);
        Arrays.sort(SangDuk_had_Bag_Info);
        
        long SangDuk_Get_Money = 0;
        int j = 0;
        
        for (int Putin = 0; Putin < SangDuk_had_Bag; Putin++) {
        
            while( (j < Jeweler_had_Jewel) && (jewel_Info[j].Jewel_Info_Weight <= SangDuk_had_Bag_Info[Putin]) ){
                priorityQueue.add(-jewel_Info[j].Jewel_Info_Price);
                j++;
            }
            
            if(!priorityQueue.isEmpty()) {
                SangDuk_Get_Money += Math.abs(priorityQueue.poll());
            }
        }

        System.out.println(SangDuk_Get_Money);
    
        inputScanner.close();


    }
}

 

jewel_Info[j].Jewel_Info_Price 에다가 마이너스를 붙히는 이유는

가방 무게보다 더 낮은것들을 큐에다가 삽입시 큐에서는 당연히 오름차순에 따라 정렬이 되는데

이를 내림차순으로 정렬해서 꺼내고싶기 때문에 -를 붙이고 꺼낼때 절댓값으로 빼기위해서 사용하는것이다.

 

c++ 언어로 푼것으로 보았을때는 q.top() 이나 q.pop()으로 바로 가장 높은값을 뺄수있지만

자바에서는 그런것이 구현이 안된것인지 ctrl+space 했을때 나오지는 않았다.

그래서 저런식으로 빼는건가 보다.

 

보석가격이 한개당 1억까지 하는 경우도있기때문에 int에다가 더할경우 초과할경우가 있다.

그렇기 때문에 long에다가 저장해준다.

 

 

 

 

 

백준문제풀이Github : 

https://github.com/sdk0213/baekjoon-study

sdk0213/baekjoon-study