백준 28339 (C++) 이상한 드래프트

최초 업로드: 2025-07-25 21:56:33

최근 수정 시간: 2025-07-25 21:56:33

게시자: rlatjwls3333

카테고리: 백준

# [Gold III] 이상한 드래프트

[문제 링크](https://www.acmicpc.net/problem/28339)

## 문제 설명

2150년, Kureyo Baseball Organization(이하 KBO)은 100번째 구단의 창단을 승인하였다. 그 전까지는 지난 시즌의 순위에 따라 지그재그식으로 한 선수씩 선발하는 식이었지만, 구단이 매우 많아지면서 드래프트가 너무 오랜 시간이 걸리게 되자 KBO는 다음과 같은 새로운 드래프트 룰을 발표하였다.

<ul>
	<li>드래프트를 신청한 선수 $N$명은 출신 학교, 대회 입상 성적, 신체 조건 등의 다양한 요소를 고려한 임의의 순서로 정렬된다.</li>
	<li>각 선수는 자신의 고유 수비 위치를 나타내는 정수인 $P_i$ ($1 ≤ P_i ≤ 9$) 와 수비 능력을 나타내는 정수인 $A_i$로 표현된다.</li>
	<li>각 구단은 자신의 드래프트 차례가 오면 선수들의 목록에서 연속된 $K$명을 뽑고 해당 선수들을 목록에서 지운다.</li>
	<li>이 때 선택된 $K$명 안에는 각 아홉 가지의 수비 위치에 대해 해당 위치를 수비할 수 있는 선수가 반드시 적어도 한 명씩 포함되어야 한다.</li>
</ul>

당신은 전년도에 꼴찌를 한 ‘쌍둥이들’의 감독으로 이번 드래프트에서 가장 먼저 $K$명의 선수를 선택하게 되었다. 쌍둥이들의 고질적 수비 불안을 해소하기 위해 다음 시즌에는 수비 능력 위주로 팀을 리빌딩할 예정이기 때문에, 이번 드래프트는 매우 중요하다.

$N$명의 선수들의 수비 위치와 수비 능력이 드래프트 신청자 목록에 주어진 순서대로 주어질 때, 각 수비 위치에서 가장 뛰어난 선수들의 능력의 총 합이 최대가 되도록 $K$명을 뽑는 프로그램을 작성하라. 단, 드래프트가 불가능한 경우는 없다고 가정한다.

## 입력

입력은 $T$개의 테스트 케이스로 구성된다. 입력의 첫 줄에는 $T$가 주어진다.

각 테스트 케이스 첫 줄에는 드래프트를 신청한 선수의 수 $N$과 드래프트로 한 번에 뽑을 수 있는 사람의 수 $K$가 공백으로 구분되어 주어진다. ($9 ≤ K ≤ N ≤ 100\,000$) 그 후 $N$줄에 각 선수들의 수비 위치 $P_i$ ($1 ≤ P_i ≤ 9$)와 수비 능력 $A_i$ ($1 ≤ A_i ≤ 100$)가 공백으로 구분되어 주어진다.

## 출력

각 테스트 케이스마다 한 줄에 하나씩 이번 드래프트에서 얻을 수 있는 각 수비 위치별로 가장 뛰어난 선수들의 수비 능력의 총 합의 최대값을 출력한다.

## 풀이
#### 범위가 더 컸다면 덱 트릭으로 풀었겠지만, 작아서 우선순위 큐로 풀었다.

``` c++
#include<bits/stdc++.h>
using namespace std;

struct element {
 int idx, a, p;
 bool operator<(const element e) const { // pq
 return a < e.a;
 }
};

const int MAX = 100'001;

vector<element> v(MAX);
vector<priority_queue<element>> pq(10);

int chk(int idx, int k) {
 int sum=0;
 for(int i=1;i<=9;i++) {
 while(!pq[i].empty() && idx-pq[i].top().idx+1>k) pq[i].pop();
 if(pq[i].empty()) return 0;
 sum += pq[i].top().a;
 }
 return sum;
}

int main() {
 ios::sync_with_stdio(0); cin.tie(0);
 int t; cin >> t;
 while(t--) {
 int n, k; cin >> n >> k;
 for(int i=0;i<n;i++) cin >> v[i].p >> v[i].a;

for(int i=1;i<=9;i++) pq[i] = {};

int maxSum=0;
 for(int i=0;i<n;i++) {
 pq[v[i].p].push({i, v[i].a});
 maxSum = max(maxSum, chk(i, k));
 }
 cout << maxSum << '\n';
 }
}
```