[백준 / BOJ] C++ 29160 나의 FIFA 팀 가치는?

29160번: 나의 FIFA 팀 가치는?

 

문제

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

29160번: 나의 FIFA 팀 가치는?

 

 

풀이

항상 가치가 가장 높은 선수를 선발하는 과정을 반복하기 때문에 우선순위 큐(최대 힙)를 사용한다.

11개의 포지션 번호별로 선수를 저장할 수 있는 우선순위 큐 배열을 만든다.

각각의 포지션 번호별로 비어있는 우선순위 큐를 제외하고 한 명씩 선수를 우선순위 큐에서 선발하고 그 선수의 가치를 1 하락한 다음 다시 우선순위 큐에 넣는 과정을 k번 반복한다. 선수의 가치는 0 미만으로 떨어지지 않음에 주의.

총 k번 반복한 후 비어있는 우선순위 큐를 제외하고 각각에서 가치가 가장 높은 선수들의 가치의 합을 출력한다.

 

 

코드

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

int main() {
  ios::sync_with_stdio(0);
  cin.tie(0);
  int n, k, ans = 0, cnt = 0;
  cin >> n >> k;
  priority_queue<int> pq[12];
  for (int i = 0; i < n; i++) {
    int p, w;
    cin >> p >> w;
    pq[p].push(w);
  }
  for (int i = 0; i < k; i++) {
    for (int j = 1; j <= 11; j++) {
      if (pq[j].empty())
        continue;
      int x = pq[j].top();
      pq[j].pop();
      pq[j].push(max(0, x - 1));
    }
  }
  for (int i = 1; i <= 11; i++) {
    if (pq[i].empty())
      continue;
    ans += pq[i].top();
  }
  cout << ans;
  return 0;
}