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

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

29160번: 나의 FIFA 팀 가치는?

코드

#include <iostream>
#include <vector>
#include <queue>
using namespace std;

vector <priority_queue<int>> v(12);
bool isexist[12];

int main()
{
	int n, k;
	long long sum = 0;
	cin >> n >> k;

	for (int i = 0, p,w; i < n; i++) {
		cin >> p >> w;
		v[p].push(w);
		if (!isexist[p]) isexist[p] = true;
	}

	for (int i = 0; i < k; i++) {
		for (int j = 1; j <= 11; j++) {
			if (isexist[j])
			{
				int tmp = v[j].top();
				if (tmp == 1) break;
				v[j].pop();
				tmp--;
				v[j].push(tmp);
			}
		}
	}

	for (int i = 1; i <= 11; i++) 
		if (isexist[i]) sum += v[i].top();

	cout << sum << "\n";
	return 0;
}

설명

최종 결과를 저장할 변수 sum을 0으로 초기화한다. 선수의 수 n과 k를 int로 선언 후 입력받는다. 반복문으로 선수의 포지션과 가치를 입력받는다. 이때 입력받은 내용은 우선순위 큐에 넣는다. 우선순위 큐를 사용하는 이유는 선수 가치가 높은 선수가 선발 선수가 되고 그 선수의 가치가 매년 8월에 떨어지므로 최대 힙을 이용해야 시간 초과가 발생하지 않는다. 선수들의 가치를 저장하는 우선순위 큐는 선수의 포지션에 따라 벡터의 p번째 원소이다. 포지션에 해당하는 선수의 존재를 저장하는 bool 타입 배열을 사용해서 빈 큐에 접근하는 일이 발생하지 않도록 한다.

 

선수들의 정보를 입력받고 나서는 반복문을 돌면서  선발 선수 선택, 선발 선수의 가치 감소를 수행한다. 해당 포지션의 선수가 있을 경우에 대해서 가장 가치가 큰 선수의 가치를 tmp에 저장한다. 그 가치가 1보다 클 경우에 대해서 pop 해주고 tmp를 1 감소시킨 값을 다시 우선순위 큐에 넣어준다.

 

k년이 지난 후 반복문을 돌면서 각 포지션에 선수가 존재할 경우 최대 가치를 가진 선수의 가치를 sum에 더해나간다. sum을 출력하고 프로그램을 종료한다.

 

느낀 점

이 문제는 SUAPC 2023 Summer문제다. 대회 당시 다른 문제들에 도전하다가 마지막에 이 문제를 풀기 시작했었다. 그래서 문제를 급하게 읽고 코드를 짜서 코드를 냈는데 시간초과가 해결이 안 됐다. 

 

대회 종료 이후 며칠 뒤에 나는 시간초과만 해결하면 된다고 생각해서 그때 생각하지 못했던 우선순위 큐를 이용해서 문제를 풀어보기 시작했다. 큐가 비어 있는 경우를 고려하지 못해서 out of bound 에러를 만났고, 그래서 bool 타입 배열로 해당 번호의 선수 존재 유무를 기록했다. 그래도 계속 잘 풀리지 않았다. 

 

최근에 다시 문제를 풀면서 기존의 코드를 수정하는 게 아니라 아예 처음부터 코드를 짰는데 통과했다.. 틀렸던 코드를 보니까 대회 당시부터 반복문의 범위를 잘못 선정했었다. 예시는 우연히 통과한 것이였고 처음부터 틀린 코드를 붙잡고 계속 맞는 곳만 수정하니 풀릴 리가 당연히 없었다.

 

코드를 천천히 뜯어보고 잘 되지 않으면 아이디어를 가지고 처음부터 다시 구현하는 것이 나을 수도 있겠다는 생각이 들었다.