
23757번: 아이들과 선물 상자
모든 아이들이 실망하지 않고 각자 원하는 만큼 선물을 가져갈 수 있으면 $1$을, 그렇지 않으면 $0$을 출력한다.
www.acmicpc.net
문제
상훈이는 N 개의 선물 상자를 가지고 있다. 선물 상자에는 현재 담겨있는 선물의 개수가 적혀있다.
선물을 받을 아이들이 M 명 있다. 아이들은 각자 1 에서 M 까지의 서로 다른 번호를 하나씩 부여받았다.
1 M 번 아이까지 한 번에 한 명씩, 현재 선물이 가장 많이 담겨있는 상자에서 각자 원하는 만큼 선물을 가져간다. 이 때, 앞서 누군가 선물을 가져갔던 선물 상자에서 또다시 가져가도 상관없다.
번 아이부터하지만 상자에 자신이 원하는 것보다 적은 개수의 선물이 들어있다면, 선물을 가져가지 못해 실망한다.
상훈이는 한 명이라도 실망하지 않고 모두가 선물을 가져갈 수 있는지 궁금하다.
입력
첫째 줄에 선물 상자의 수 N 과 아이들의 수 M이 공백을 사이에 두고 주어진다. (1 <= M <= N <= 10^5)
둘째 줄에 각 선물 상자에 들어있는 선물의 개수 c1, c2, ... cn이 공백을 사이에 두고 주어진다. (1<= ci <= 10^5)
셋째 줄에 아이들의 번호 순으로 각 아이가 원하는 선물의 개수 w1, w2, ... wm이 공백을 사이에 두고 주어진다. (1<= wi<= 10^5)
출력
모든 아이들이 실망하지 않고 각자 원하는 만큼 선물을 가져갈 수 있으면 1을, 그렇지 않으면 0을 출력한다.
풀이
우선순위 큐를 이용하여 항상 가장 많은 사탕을 가지는 상자를 유지함.
각 아이들이 요구하는 선물을 가져간다.
이 때 가장 많은 사탕을 들고 있는 상자에서 가져갈만큼의 사탕을 뺀 후 다시 큐에 넣어서
상자의 순서를 유지시킨다.
for문을 이용해서 가장 마지막 아이까지 사탕을 가져간다면 1을 출력, 가져가지 못하면 0을 출력한다.
코드
import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws Exception{ BufferedReader br = new BufferedReader(new InputStreamReader(System.in)); StringTokenizer st = new StringTokenizer(br.readLine()); int n = Integer.parseInt(st.nextToken()), m = Integer.parseInt(st.nextToken()), i=0; PriorityQueue<Integer> gift = new PriorityQueue<Integer>(Collections.reverseOrder()); // 선물은 지속적으로 가장 큰 선물 상자를 이용하기에 우선순위큐를 내림차순으로 이용하여 head부분에 항상 가장 큰 선물 개수가 오도록 함 int [] child = new int[m]; // 학생들은 부여된 순서대로 선물을 챙김 st = new StringTokenizer(br.readLine()); for(i=0;i<n;i++) gift.add(Integer.parseInt(st.nextToken())); st = new StringTokenizer(br.readLine()); for(i=0;i<m;i++) child[i] = Integer.parseInt(st.nextToken()); i=0; while(i<m && gift.size()>0) { if(child[i]==gift.peek()) { // 학생이 원하는 선물의 개수와 현재 최대 선물 개수가 동일하다면 학생번호를 증가시키고 선물을 삭제 i++; gift.poll(); }else if(child[i]<gift.peek()) // 최대 선물 개수가 더 크다면 선물을 가져가고 남은 선물을 다시 큐에 삽입 gift.add(gift.poll()-child[i++]); else // 선물을 못가져 간다면 아이들이 실망하면서 종료 break; } if(i==m) // 학생들이 증가해서 마지막학생까지 선물을 가져갔다면 1을 출력 System.out.println(1); else System.out.println(0); } }
'Algorithm > Baekjoon' 카테고리의 다른 글
Baekjoon 10813 공 바꾸기 JAVA (0) | 2022.09.15 |
---|---|
Baekjoon 11719 그대로 출력하기 2 JAVA (0) | 2022.09.14 |
Baekjoon 25328 문자열 집합 조합하기 JAVA (0) | 2022.09.14 |
Baekjoon 24509 상품의 주인은? JAVA (0) | 2022.09.07 |
Baekjoon 19575 Polynomial JAVA (0) | 2022.09.07 |
댓글