[자바] 백준 23757 - 아이들과 선물 상자 (java)

 문제 : boj23757

---

 

필요 알고리즘 개념

• 우선순위 큐 (priority queue) 또는 max heap
  
  • 우선순위 큐로 시작해서 우선순위 큐로 끝나는 문제이다.

※ 제 코드에서 왜 main 함수에 로직을 직접 작성하지 않았는지, 왜 Scanner를 쓰지 않고 BufferedReader를 사용했는지 등에 대해서는 '자바로 백준 풀 때의 팁 및 주의점' 글을 참고해주세요. 백준을 자바로 풀어보려고 시작하시는 분이나, 백준에서 자바로 풀 때의 팁을 원하시는 분들도 보시는걸 추천드립니다.

 

---

 

풀이

  대놓고 우선순위 큐(이하 pq) 문제이다. 다만, 가장 큰 값부터 꺼내져야하므로 pq 또한 최대값을 기준으로 꺼내질 수 있도록 해줘야 한다. 자바의 경우 new PriorityQueue<>(Collections.reverseOrder()); 처럼 선언 시 그렇게 사용할 수 있다.

 

  로직은 다음과 같다.

1. N개의 ci를 입력받아 전부 pq에 넣는다.

2. M개의 wi를 입력받으면서 w1부터 wM 까지 순서대로 '3'을 진행한다.

3. pq에서 하나를 꺼낸다. 현재 보고 있는 w값이 pq에서 꺼낸 값보다 크다면 불가능한 경우이니 0을 출력하고 끝낸다.

4. w값이 pq에서 꺼낸 값보다 작거나 같다면, '꺼낸 값 - 현재 w값'을 다시 pq에 넣는다.

 

  위의 로직이 M개의 w값에 대해 모두 진행 가능하다면 1을 출력해주면 된다

 

 

---

 

코드 : github

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Collections;
import java.util.PriorityQueue;
import java.util.StringTokenizer;

public class Main {
    private void solution() throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int n = Integer.parseInt(st.nextToken());
        int m = Integer.parseInt(st.nextToken());
        PriorityQueue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; i++) {
            pq.add(Integer.parseInt(st.nextToken()));
        }
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < m; i++) {
            int cur = Integer.parseInt(st.nextToken());
            int max = pq.poll();
            if (cur > max) {
                System.out.println(0);
                return;
            }
            pq.add(max-cur);
        }
        System.out.println(1);
    }

    public static void main(String[] args) throws Exception {
        new Main().solution();
    }
}