[백준] 알고리즘 분류(그리디 알고리즘,JAVA)1202번, 보석 도둑

 

문제 링크

1202번: 보석 도둑

---

주의사항

• JAVA를 사용하여 프로그램을 사용하였습니다.
• 백준에서 코드를 작성하였을 때 아래 형태에서 Main에서 결과가 출력되어야 합니다.

public class Main{ 	
	public static void main(String[] args){
    }
}

---

문제 설명

---

접근 방법

이 문제에 핵심

 

1. 가방에는 보석을 1개만 담을 수 있습니다.

2. 가방에는 담을 수 있는 보석의 최대 무게가 주어집니다.

3. K개의 가방에 보석을 넣었을 때 보석의 가치가 최대가 되는 값을 결과로 출력합니다.

4. 모든 숫자는 양수입니다.

 

알고리즘 진행 순서.

 

1. 입력된 정보를 저장합니다.

 

2. 가방 및 보석에 대하여 정렬한 뒤, 가방에 보석을 넣습니다.

 

3. 가방에 넣은 보석들의 가치의 합을 결과로 출력합니다. 

 

 

정렬.

 

가방에 보석을 넣을 때 큰 가방부터 탐색하면 작은 가방에 넣을 수 없는 경우가 발생합니다.

 

가방은 오름차순 정렬!

 

가방을 오름차순으로 정렬하였기 때문에 보석도 무게가 낮은 것부터 탐색하고, 가치의 최대값을 구해야하기 때문에 무게가 같을 때에는 가치가 높은 것을 먼저 탐색해야 합니다.

 

보석은 무게를 기준으로 오름차순 정렬!보석의 무게가 같을 때는 가치를 기준으로 내림차순 정렬!

 

보석을 가방에 넣기.

 

PriorityQueue를 사용하여 가방에 넣을 수 있는 보석들을 확인하였습니다.

※최대값을 구해야하기 때문에 내림차순으로 정렬되는 PriorityQueue를 사용합니다.

 

1) 작은 가방부터 넣을 수 있는 보석들의 가치를 저장합니다.

 

2) 넣을 수 있는 보석을 다 넣었을 때 PriorityQueue에 값이 존재하면 poll()을 진행하여 가장 큰 가치값을 가져옵니다.

 

3) 위 과정을 모든 가방에 대하여 반복합니다.

 

※이 방법을 사용하면 보석에 대하여 반복적으로 탐색할 필요없이 한 번씩만 탐색이 가능합니다.

 

예제를 진행하는 과정을 살펴보시면 이해하시기 편하실 것입니다.

 

예제입력 2.

 

1. 입력된 정보를 저장합니다.

 

N : 3

K : 2

 

보석

무게	가치
1	65
5	23
2	99

가방

가방1	가방2
10	2

 

2. 가방 및 보석에 대하여 정렬한 뒤, 가방에 보석을 넣습니다.

 

가방 오름차순 정렬!

 

가방2	가방1
2	10

 

보석 정렬!

 

무게	가치
1	65
2	99
5	23

 

가방 보석의 넣기!

 

1) 작은 가방부터 넣을 수 있는 보석들의 가치를 저장합니다.

 

가방2 넣을 수 있는 보석 PriorityQueue 저장

99(무게 : 2)

65(무게 : 1)

※무게 : 5, 가치 : 23인 보석은 가방에 무게보다 크기 때문에 저장하지 않습니다.

 

2) 넣을 수 있는 보석을 다 넣었을 때 PriorityQueue에 값이 존재하면 poll()을 진행하여 가장 큰 가치값을 가져옵니다.

 

가장 큰 가치 : 99(무게 : 2)보석을 가방2에 넣기

 

3) 위 과정을 모든 가방에 대하여 반복합니다.

 

1)) 작은 가방부터 넣을 수 있는 보석들의 가치를 저장합니다.

가방1 넣을 수 있는 보석 PriorityQueue 저장

65(무게 : 1)

23(무게 : 5)

2)) 넣을 수 있는 보석을 다 넣었을 때 PriorityQueue에 값이 존재하면 poll()을 진행하여 가장 큰 가치값을 가져옵니다.

가장 큰 가치 : 65(무게 : 1)보석을 가방1에 넣기

 

3. 가방에 넣은 보석들의 가치의 합을 결과로 출력합니다. 

 

가방1(65) + 가방2(99) = 65 + 99 = 164

164을 결과로 출력합니다.

 

• BufferedReader를 사용하여 입력되는 정보를 저장합니다.
• StringTokenizer를 사용하여 보석에 대한 정보를 띄어쓰기 기준 나누었습니다.
• Arrays.sort로 가방과 보석에 대하여 정렬을 하였습니다.
• PriorityQueue를 이용하여 가방의 무게가 낮은 것부터 넣을 수 있는 보석을 탐색하여 가치가 높은 보석을 넣습니다.
• 가방에 넣은 보석 가치의 합을 결과로 BufferedWriter 저장하였습니다.
• BufferedWriter에 저장된 결과값을 출력하였습니다.

 

import java.io.*;
import java.util.*;

public class Main {
    //보석 관련 정보 클래스
    static class jewel implements Comparable<jewel> {
        int value, weight;	//가치 및 무게
        //생성자
        public jewel(int value, int weight){
            this.value = value;
            this.weight = weight;
        }
        //보석 클래스 정렬 관련
        @Override
        public int compareTo(jewel o) {
            if(this.weight == o.weight)		//무게가 같을 때 가치 내림차순
                return o.value - this.value;
            return this.weight - o.weight;	//무게 오름차순
        }
    }
    static int N,K;
    static long answer = 0;
    static int[] bag;	//가방 무게 저장 배열
    static jewel[] jewels;	//보석 저장 배열
    public static void main(String[] args) throws IOException {
        //입력값 처리하는 BufferedReader
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //결과값 출력하는 BufferedWriter
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine()," ");
        N = Integer.parseInt(st.nextToken());
        K = Integer.parseInt(st.nextToken());
        bag = new int[K];
        jewels = new jewel[N];
        //보석 입력값 저장
        for(int i=0;i<N;i++){
            st = new StringTokenizer(br.readLine()," ");
            int M = Integer.parseInt(st.nextToken());
            int V = Integer.parseInt(st.nextToken());
            jewels[i] = new jewel(V, M);
        }
        //가방 입력값 저장
        for(int i=0;i<K;i++){
            int C = Integer.parseInt(br.readLine());
            bag[i] = C;
        }
        Arrays.sort(bag);	//가방 오름차순 정렬
        Arrays.sort(jewels);	//보석 정렬
        //PriorityQueue 생성 및 내림차순 정렬로 설정
        PriorityQueue<Integer> pq = new PriorityQueue<>(Comparator.reverseOrder());
        //가방 무게가 낮은 것부터 탐색.
        for(int i=0,j=0;i<K;i++){
            while(j<N){
                if(bag[i] < jewels[j].weight)	//다음 보석부터 가방의 무게보다 클 때
                    break;
                pq.add(jewels[j++].value);	//가방에 보석을 넣을 수 있을 때
            }
            //넣을 수 있는 보석이 있을 때 가장 가치가 높은 것 넣기
            if(!pq.isEmpty())
                answer += pq.poll();
        }
        bw.write(answer + "");		//가치의 합 BufferedWriter 저장
        bw.flush();		//결과 출력
        bw.close();
        br.close();
    }
}