[java]백준 25391번- 특별상

https://www.acmicpc.net/problem/25391

25391번: 특별상

 

코드

 

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

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());
		int K = Integer.parseInt(st.nextToken());

		//	본상을 K개 수여하기 위해 심판의 최대점수로 내림차순을 위한 우선순위 큐
		PriorityQueue<Score> sc = new PriorityQueue<Score>();
		
		for (int i = 0; i < N; i++) {
			st = new StringTokenizer(br.readLine());
			int a = Integer.parseInt(st.nextToken());
			int b = Integer.parseInt(st.nextToken());
			;
			sc.add(new Score(a, b));
		}

		long sum = 0;
		// 본상 K개를 심판 최대점수 내림차순에서 더해준다.
		for (int i = 0; i < K; i++) {
			sum += sc.poll().a;
		}
	
		//주최자가 주는 특별상은 주최자 최대점수로 남은 학생들을 내림차순한다.ㅇ 우선순위 큐 사용해
		PriorityQueue<Integer> a = new PriorityQueue<>(Collections.reverseOrder());

		while (!sc.isEmpty()) { // 전에 큐가 빌 때까
			a.add(sc.poll().a);
		}
        
		//주최자 최대점수 내림차순한 것을 M개 더해준다.2
		for (int i = 0; i < M; i++) {

			sum += a.poll();
		}

		System.out.println(sum);

	}

}

class Score implements Comparable<Score> {
	int a;
	int b;

	Score(int a, int b) {
		this.a = a;
		this.b = b;
	}

	public int compareTo(Score s) {
		if (this.b > s.b)
			return -1;
		else
			return 1;
	}

}

 

 

풀이

1. 심판의 점수순(내림차순)으로 본상을 먼저 구해준다

-> 심판의 점수와 주최자의 점수를 클래스 Score를 사용해서 심판 점수순(내림차순)으로 우선순위큐에 저장해둔다.

-> 심판의 본상 K개 만큼 우선순위큐 sc에서 poll해서 주최자의 점수를 sum에 더해준다.

 

2. k개 저장후 본상 M개를 위해 sc에 남은 점수들을 우선순위큐 a에 주최자의 점수 a만 저장한다(내림차순). (a(주최자의 점수)만 사용할거기 때문에)

-> 우선순위큐 a에서 M개 poll해서 sum에 더해준다.