BOJ_보석도둑_1202 (Java, C++)

문제 링크

성능 요약

Java - 메모리:115196 KB, 시간: 1716 ms
C++ - 메모리:11696 KB, 시간: 416 ms

분류

자료 구조, 그리디 알고리즘, 우선순위 큐, 정렬

제출 일자

2024년 12월 16일 17:11:06

문제 설명

세계적인 도둑 상덕이는 보석점을 털기로 결심했다.

상덕이가 털 보석점에는 보석이 총 N개 있다. 각 보석은 무게 Mi와 가격 Vi를 가지고 있다. 상덕이는 가방을 K개 가지고 있고, 각 가방에 담을 수 있는 최대 무게는 Ci이다. 가방에는 최대 한 개의 보석만 넣을 수 있다.

상덕이가 훔칠 수 있는 보석의 최대 가격을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N과 K가 주어진다. (1 ≤ N, K ≤ 300,000)

다음 N개 줄에는 각 보석의 정보 Mi와 Vi가 주어진다. (0 ≤ Mi, Vi ≤ 1,000,000)

다음 K개 줄에는 가방에 담을 수 있는 최대 무게 Ci가 주어진다. (1 ≤ Ci ≤ 100,000,000)

풀이

• 느낀점: 그리디가 무작정 유리한대로 고르기만 하는 쉬운 알고리즘은 아닌 것 같다. 그 유리한 방식을 효과적으로 어떻게 활용할지가 관건이다. 연습이 많이 필요할 것 같다.

• 설계 시간: 30분고민해보고 1차 실패, 이후에는 참고했다.

  💡 설계 아이디어

  • 처음에는 그냥 단순히 가방을 무게 오름차순으로 순회하면서 보석을 가치순 우선으로 정렬해놓고 큰 가치중에 적절한 보석을 찾으면 넣도록 했다.
  • 사실 고민을 안한 풀이라고 봐도됨,, 그냥 전탐이잖아
  • 참고한 풀이
    • 보석을 무게 오름차순으로 정렬한다.
    • 가방을 오름차순으로 정렬하고 순회한다.
    • 가방에 들어갈 수 있는 보석을 전부 Priority Queue에 넣고 가치 내림차순으로 정렬한다.
    • 큐에 보석이 1개 이상 있다면 하나 뽑아서 answer에 더한다.

코드

• 구현 시간: 40분 (java)

/**
 * Author: yngbao97, Yuk Yejin
 * Problem: 보석 도둑_1202
 * Date: 2024.12.15
 */

import java.lang.reflect.Array;
import java.util.*;
import java.lang.*;
import java.io.*;

public class Main {
	static BufferedReader br;
	static BufferedWriter bw;
	static StringTokenizer st;

	public static void main(String[] args) throws Exception {

		br = new BufferedReader(new InputStreamReader(System.in));
		bw = new BufferedWriter(new OutputStreamWriter(System.out));
		
		String[] input = br.readLine().split(" ");
        int n = Integer.parseInt(input[0]);     // 보석의 개수
        int k = Integer.parseInt(input[1]);     // 가방의 개수

        Jewelry[] jewelries = new Jewelry[n];
        for (int i = 0; i < n; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            int weight = Integer.parseInt(st.nextToken());
            int value = Integer.parseInt(st.nextToken());
            jewelries[i] = new Jewelry(weight, value);
        }

        int[] bags = new int[k];
        for (int i = 0; i < k; i++) {
            bags[i] = Integer.parseInt(br.readLine());
        }

        Arrays.sort(jewelries, (o1, o2) -> {
            return o1.weight - o2.weight;
        });
        Arrays.sort(bags);

        PriorityQueue<Jewelry> candidate = new PriorityQueue<>((o1, o2) -> {
            return o2.value - o1.value;
        });
        int jIdx = 0;
        long answer = 0L;
        for (int w : bags) {
            while (jIdx < n && jewelries[jIdx].weight <= w) candidate.add(jewelries[jIdx++]);
            if (candidate.isEmpty()) continue;
            int value = candidate.poll().value;
            answer += value;
        }

        bw.write(String.valueOf(answer));
		
		bw.flush();
		bw.close();
		br.close();
	}
}

class Jewelry {
    int weight;
    int value;

    Jewelry (int weight, int value) {
        this.weight = weight;
        this.value = value;
    }
}

• 구현 시간: 90분 (c++)

/**
 * Author: yngbao97, Yuk Yejin
 * Problem: 보석 도둑_1202
 * Date: 2024.12.16
 */

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>

using namespace std;

class Jewelry {
    public:
        int weight;
        int value;

        Jewelry() : weight(0), value(0) {}
        Jewelry(int w, int v) : weight(w), value(v) {}
};

struct CompareWeight {
    bool operator() (const Jewelry& j1, const Jewelry& j2) {
        return j1.weight < j2.weight;
    }
};

struct CompareValue {
    bool operator() (const Jewelry& j1, const Jewelry& j2) {
        return j1.value < j2.value;
    }
};

int main() {

    int n, k;
    cin >> n >> k;

    vector<Jewelry> jewelries(n);
    for (int i = 0; i < n; i++) {
        cin >> jewelries[i].weight >> jewelries[i].value;
    }

    vector<int> bags(k);
    for (int i = 0; i < k; i++) {
        cin >> bags[i];
    }

    sort(jewelries.begin(), jewelries.end(), CompareWeight());
    sort(bags.begin(), bags.end());

    priority_queue<Jewelry, vector<Jewelry>, CompareValue> candidate;
    int idx = 0;
    long answer = 0;
    for (int b : bags) {
        while (idx < n && b >= jewelries[idx].weight) candidate.push(jewelries[idx++]);
        
        if (candidate.empty()) continue;
        answer += candidate.top().value;
        candidate.pop();
    }

    cout << answer << endl;
}

• 알게된 점
  - sort함수와 priority_queue의 기본 정렬방식이 다르기 때문에 각각을 통해 정렬을 정의할때 유의해야 한다.
  - 코드를 보면 CompareWeight와 CompareValue가 동일한 형태로 정의 되었지만, CompareWeight는 무게 오름차순, CompareValue는 가치 내림차순으로 사용되고 있는 걸 알 수 있다.
  - sort함수는 기본적으로 오름차순의 구조를 갖기 때문에 비교함수에서 true를 반환하면 순서를 유지한다. 따라서 j1.weight < j2.weight 가 true를 반환하면 더 작은 요소가 앞에 위치한다.
  - priority_queue는 기본적으로 최대힙으로 구현되며, 비교함수에서 true를 반환하면 두 요소의 순서를 바꾼다. 따라서 j1.value < j2.value 가 true를 반환하면 더 큰 요소가 앞에 위치한다.

  즉,
  std::sort는 비교 함수에서 "왼쪽 값이 오른쪽 값보다 작다"라고 판단(true)하면 그대로. 따라서 오름차순
  std::priority_queue는 비교 함수에서 "왼쪽 값이 오른쪽 값보다 작다"라고 판단(true)하면 두 값의 우선순위를 바꿈. 따라서 내림차순

• 유의할 점
  • 어떤 자료구조가 어떤 헤더에 있는 표준 라이브러리인지 알고 include를 반드시 해주어야 한다.