[BaekJoon/Java] 백준 1202 보석도둑

김시현 Si Hyeon, Kim·2022년 1월 16일
0

Algorithm

목록 보기
7/9
post-custom-banner

문제 요약 설명

가방 K개가 주어질 때, 하나의 가방에는 정해진 무게까지의 보석만 담을 수 있다. 그렇다면 보석 N개를 가방 K개에 담아서 훔칠 수 있다면 훔친 보석 가격이 최대가 되게 만들어야 한다.

아이디어

보석 N개를 무게 순으로 오름차순 정렬하고, 가방도 담을 수 있는 무게에 따라서 오름차순 정렬한다. 보석의 가격이 최대가 되기 위해선 가방에 담을 수 있는 보석중에서 가장 비싼 보석을 담으면 된다. 이 때 가방을 기준으로 가장 작은 무게를 담을 수 있는 가방부터 탐색하게 되는데, 이유는 다음과 같은 반례로 예를 들 수 있다.

ex)
보석 1: 무게 1, 가격 99
보석 2: 무게 99 가격 1

가방 - 1, 99
의 경우 무거운 가방 순서로 탐색을 하면 99에 가장 비싼 보석(보석 1)을 담고, 그 다음 1짜리 가방에는 아무것도 담지 못해서 총 가격 99가 된다.

하지만 가벼운 가방 순서로 탐색을 하면 1에 가장 비싼 보석(보석 1)을 담고, 그다음 99짜리 가방에 무게 99짜리 보석(보석 2)을 담아서 총 가격은 100이 된다.

풀이

  1. 보석을 무게 순으로 오름차순 정렬한다. 이 때 보석의 무게가 같지만 가격이 다르면 가격이 작은 녀석이 앞으로 오게 된다.
  2. 가방을 가벼운 순서가 앞으로 오도록 오름차순 정렬한다.
  3. for 문으로 1~K까지 가방을 탐색한다.
  4. 우선순위큐를 만든다(힙도 가능). 해당 큐는 보석의 가격이 클 수록 앞으로 오게된다. 힙으로 따지면 max 힙을 생성한다.
  5. 가방 i번째일때, 보석 1~N개 중에 가방 i에 담을 수 있는 보석들의 가격을 전부 우선순위 큐에 담는다. 이 때, 1~j까지의 보석이 검출 되었다고 하자. 그러면 가장 비싼 보석이 우선순위 큐의 0번째 index에 위치하게 되는데 해당 값을 pop 해서 result에 더해준다.
  6. 큐를 비울 필요 없이 다음 가방 무게로 넘어가서 다시 해당 가방에 담을 보석들을 탐색하게 되는데 5번의 과정에서 j까지의 보석은 이미 큐에 담았으므로, j+1부터 보석들을 담기 시작한다.
  7. result 에 담겨있는 값을 출력한다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.*;

public class Main {
    // 보석 행렬
    public static int[][] acce;
    // 가방은 벡터 어레이로
    public static ArrayList<Integer> bag;
    // 최대 힙으로 쓸 녀석
    public static PriorityQueue<Integer> queue = new PriorityQueue<>(Collections.reverseOrder());


    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = null;
        st = new StringTokenizer(br.readLine());

        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());

        acce = new int[N][2];
        bag = new ArrayList<>();

        for (int i = 0; i < N; i++) {
            st = new StringTokenizer(br.readLine());
            acce[i][0] = Integer.parseInt(st.nextToken());
            acce[i][1] = Integer.parseInt(st.nextToken());
        }

        Arrays.sort(acce, (o1, o2) -> {
            if(o1[0] == o2[0]) return Integer.compare(o1[1], o2[1]);
            else return Integer.compare(o1[0], o2[0]);
        });

        for (int i = 0; i < K; i++) {
            bag.add(Integer.parseInt(br.readLine()));
        }
        bag.sort(Comparator.naturalOrder());

        long result = 0;
        int idx = 0;

        for(int i = 0; i < K; i++) {
            int M = bag.get(i);
            while(idx < N && acce[idx][0] <= M) {
                queue.add(acce[idx][1]);
                idx++;
            }
            if (queue.size() != 0) {
                result = (long) result + queue.poll();
            }
        }
        System.out.print(result);
        br.close();
    }
}
profile
최악의 환경에서 최선을 다하자!!
post-custom-banner

0개의 댓글