[Algo] 백준 23757 아이들과 선물상자 JAVA

문제 바로가기 : https://www.acmicpc.net/problem/23757

메모리 : 35372KB

시간 : 504 ms

언어 : Java 11

---

코드

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

public class Main {
    public static void main(String[] args) throws IOException {
        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());
        st = new StringTokenizer(br.readLine());
        PriorityQueue<Integer> box = new PriorityQueue<>(Collections.reverseOrder());
        for (int i = 0; i < N; i++) {
            box.add(Integer.parseInt(st.nextToken()));
        }
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < M; i++) {
            int now = box.poll();
            int want = Integer.parseInt(st.nextToken());
            if (now < want) {
                System.out.println(0);
                return;
            }
            box.add(now - want);
        }
        System.out.println(1);

    }
}

 

풀이

우선순위 큐를 이용하는 간단한 문제. 

"현재 선물이 가장 많이 담겨있는 상자" 라는 말은 선물을 뽑을 때 마다, 즉 상자 속 선물의 개수가 줄어들때마다 재정렬을 해서 선물이 가장 많이 담겨있는 상자를 찾으라는 말이다. 우선순위 큐를 이용해 실시간으로 상자를 재정렬하며 해당 상자에서 선물을 다 가져가 수 있는지만 확인해주면 된다.