[백준] S3 12018 Yonsei TOTO (java)

www.acmicpc.net/problem/12018

12018번: Yonsei TOTO

 

풀이

 

1) PriorityQueue queue에 각 과목을 수강하기위한 최소 마일리지를 담을거임.

2) PriorityQueue pq (내림차순)에 신청인원들이 넣은 마일리지를 담는다

3) 경우를 나누어 따져본다.

3-1) 신청인원 >= 수강인원 : pq에서 수강인원수 만큼 뽑고 가장 마지막에 뽑은 마일리지 +1을 queue에 담는다.

3-2) 신청인원 < 수강인원 : queue에 1을 담는다. (마일리지 1만 있어도 수강할 수 있음)

4) 마일리지 < queue.poll() 일 때까지 queue.poll을 마일리지에서 빼고 answer++

5) answer 출력

 

주의사항

 

1) pq는 Collections.reverseOrder()를 써야함

 

 

package com.baekJoon;

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

public class BJ_S3_12018_YonseiTOTO {
	static BufferedReader input = new BufferedReader(new InputStreamReader(System.in));
	static StringTokenizer tokens;
	static int N, M;
	public static void main(String[] args) throws NumberFormatException, IOException {
		input = new BufferedReader(new StringReader(src));
		tokens = new StringTokenizer(input.readLine());
		N = Integer.parseInt(tokens.nextToken());
		M = Integer.parseInt(tokens.nextToken());
		Queue<Integer> queue = new PriorityQueue<Integer>();
		for(int n=0; n<N; n++) {
			tokens = new StringTokenizer(input.readLine());
			int P = Integer.parseInt(tokens.nextToken());
			int L = Integer.parseInt(tokens.nextToken());
			
			tokens = new StringTokenizer(input.readLine());
			Queue<Integer> pq = new PriorityQueue<>(Collections.reverseOrder());
			for(int p=0; p<P; p++) {
				pq.offer(Integer.parseInt(tokens.nextToken()));
			}
			if(P >= L) {
				for(int l=0; l<L-1; l++) {
					pq.poll();
				}
				queue.offer(pq.poll());
			}else {
				queue.offer(1);
			}
		}
		int answer = 0;
		while(!queue.isEmpty()) {
			int temp = queue.poll();
			
			if(M >= temp) {
				M -= temp;
				answer++;
			}else {
				break;
			}
		}
		System.out.println(answer);
	}

	static String src =
			"5 76\r\n" + 
			"5 4 \r\n" + 
			"36 25 1 36 36\r\n" + 
			"4 4\r\n" + 
			"30 24 25 20\r\n" + 
			"6 4\r\n" + 
			"36 36 36 36 36 36\r\n" + 
			"2 4\r\n" + 
			"3 7\r\n" + 
			"5 4\r\n" + 
			"27 15 26 8 14";
}

 

 

후기

 

 그리디문제를 찾다가 풀게된 문제이다. 하지만 그리디의 성격보다는 정렬과 PriorityQueue의 성격이 더 짙은 문제였다.

그래도 이번 기회에 Collections.reverseOrder()를 머리속에 각인 시키게 되었다.