문제 풀이
그리디
queue1 = 심판이 부여한 점수에 따라 학생이 정렬되는 큐
queue2 = 주최자가 부여한 점수에 따라 학생이 정렬되는 큐
answer = 상을 받은 학생이 받은 주최자가 부여한 점수의 합 중 최댓값
심판이 부여한 점수가 가장 높은 K명의 학생은 주최자가 수상하는 특별상을 수상하지 않아도 심판이 수상하는 본상을 받기 때문에 항상 상을 받음
따라서 주최자가 수상하는 특별상은 심판이 부여한 점수가 가장 높은 K명의 학생을 제외하고 주최자가 부여한 점수가 가장 높은 M명을 뽑아야 주최자가 부여한 점수의 최댓값이 커짐
따라서 N명의 학생에 대해 주최자가 부여한 점수가 a, 심판이 부여한 점수가 b라고 하면 심판이 부여한 점수를 기준으로 정렬하는 queue1에 학생들을 저장함
그 이후 queue1에서 K명을 뽑아 주최자가 부여한 점수 a를 answer에 더해주고 나머지 queue1에 저장된 모든 학생을 queue2에 저장해 상을 받지 못한 모든 학생을 저장함
그러면 본상을 받을 K명을 제외한 학생이 queue2에 저장되어 있으므로 M명을 뽑아 주최자가 보여한 점수 a를 answer에 더해줌
그러면 answer에 주최자가 부여한 점수의 합 중 최댓값이 저장되므로 출력하면 정답
풀이 설명
N 명의 학생 중 주최자가 M명의 특별상, 심판이 K명의 본상을 뽑을 때 상을 받는 모든 학생에 대해 주최자가 매긴 점수의 합이 최대로 되도록 뽑았을 때 합의 최댓값을 구하는 문제이다.
먼저 주최자가 M명을 먼저 뽑은 뒤 심판이 남은 인원 중 심판이 부여한 점수가 가장 높은 K명을 본상으로 추첨하기 때문에 심판이 부여한 점수가 가장 높은 K명은 주최자가 뽑아도 상을 받게 되고, 주최자가 뽑지 않으면 심판이 상을 부여하기 때문에 항상 뽑히는 인원이 된다.
따라서 주최자가 매긴 점수의 합이 최대로 되도록 뽑으려면 주최자가 뽑는 M명이 심판이 부여한 점수가 가장 높은 K명을 제외한 인원 중 주최자가 매긴 점수의 합이 가장 높은 M명을 뽑으면 된다.
즉, 심판이 부여한 점수가 가장 높은 K명을 뽑고 나머지 인원 중 주최자가 부여한 점수가 가장 높은 M명을 뽑아 이들의 주최자가 부여한 점수의 합을 출력하면 된다.
따라서 이에 맞게 사람을 뽑으려면 심판이 부여한 점수를 기준으로 내림차순으로 정렬해 K명을 뽑고, 주최자가 부여한 점수를 기준으로 내림차순으로 정렬해 M명을 뽑아야 한다.
여기서 K명, M명을 뽑기 위해 배열을 사용해 정렬하게 된다면 N명이 저장된 배열 전체를 2번 정렬해야 한다. 하지만 K명, M명을 뽑기 위해 전체를 정렬하기 보다 힙 구조를 만들어 최댓값, 최솟값을 뽑을 수 있는 PriorityQueue를 이용하면 전체를 정렬하지 않고 K명, M명을 뽑을 수 있기 때문에 더 빠르게 인원을 뽑을 수 있다.
이에 따라 심판이 부여하는 점수를 기준으로 정렬하는 큐를 queue1, 주최자가 부여하는 점수를 기준으로 정렬하는 큐를 queue2로 정의하고 N명의 학생에 대해 주최자가 부여한 점수 a와 심판이 부여한 점수 b를 queue1에 모두 저장한다. 그리고 정답을 저장할 변수 answer를 0으로 초기화한다.
queue1에서 본상을 받을 K명을 꺼내어 그 학생이 주최자에게 받은 점수 a를 answer에 더해주어 본상을 받는 모든 학생의 주최자가 부여한 점수의 합을 answer에 반영한다. 그러고 나서 상을 받지 못한 나머지 학생 중 주최자가 부여한 점수가 가장 높은 M명을 뽑기 위해 queue1에 남은 모든 학생을 queue2에 저장한다.
queue2에서 특별상을 받을 M명을 꺼내어 그 학생이 주최자에게 받은 점수 a를 answer에 더해주면 answer에 주최자가 부여한 점수의 합 중 최댓값이 되므로 출력하면 정답이 된다.
소스 코드
import java.io.StreamTokenizer
import java.util.PriorityQueue
fun main() = StreamTokenizer(System.`in`.bufferedReader()).run {
fun nextInt(): Int{
nextToken()
return nval.toInt()
}
val N = nextInt()
var M = nextInt()
var K = nextInt()
val queue1 = PriorityQueue<IntArray>{o1, o2 -> o2[1] - o1[1]}
val queue2 = PriorityQueue<IntArray>{o1, o2 -> o2[0] - o1[0]}
for(i in 0 until N){
val arr = intArrayOf(nextInt(), nextInt())
queue1.add(arr)
}
var answer = 0L
while(K > 0){
val (a, _) = queue1.poll()
answer += a
K--
}
queue2.addAll(queue1)
while(M > 0){
val (a, _) = queue2.poll()
answer += a
M--
}
println(answer)
}