[Baekjoon] 23757_아이들과 선물 상자

Silver II

문제(출처: https://www.acmicpc.net/problem/23757)

---

< 아이들과 선물 상자 >

 

문제 풀이 

 

우선순위 큐를 사용해서 상자에 자신이 원하는 것보다 적게 들어있는지 확인한다.

 

 my solution (Java)

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

public class _23757_ { // 아이들과 선물 상자 

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

		int n = Integer.parseInt(st.nextToken());
		int m = Integer.parseInt(st.nextToken());

		PriorityQueue<Integer> queue = new PriorityQueue<>(Collections.reverseOrder());
		st = new StringTokenizer(bf.readLine());
		for (int i = 0; i < n; i++) {
			queue.add(Integer.parseInt(st.nextToken()));
		}

		st = new StringTokenizer(bf.readLine());
		boolean flag = false;
		for (int i = 0; i < m; i++) {
			int num = Integer.parseInt(st.nextToken());
			int box = queue.poll();
			if (box < num) {
				flag = true;
				break;
			}
			queue.add(box - num);
		}
		if (flag)
			System.out.println(0);
		else
			System.out.println(1);
	}
}

 

Main

변수)
n : 선물 상자의 수
m : 아이들의 수
queue : 우선순위 큐 (내림차순)
flag : 모든 아이들이 원하는 만큼 선물을 가져갈 수 있는지 여부

 

- 선물 상자의 수 (n), 아이들의 수(m) 입력

- 각 상자에 들어있는 선물의 수를 입력받아 queue에 저장

- 아이가 원하는 선물의 개수를 입력받아 queue의 첫 번째 값보다 적게 원하면 뺀 값을 다시 queue에 저장 But 첫 번째 값 보다 큰 값을 원하면 선물을 가져가지 못하므로 종료

- flag 여부에 따라 답 출력

---

---