codeground 프로그래밍 경진대회

[ 해결 방법 ]

마지막 라운드에서 본인은 최고점을 받고 다른 사람들의 점수보다 크거나 같은지 판단하면된다.

이를 위해서, 우선 입력받은 점수를 오름차순으로 정렬한다.

현재 라운드까지 높은 점수를 받은 사람일 수록 마지막 라운드에서는 낮은 점수를 받아야한다.

그래서, 현재 라운드 1등은 1점, 2등은 2점, 3등은 3점처럼 점수를 준다.

현재 라운드에서 자기보다 낮은 점수의 사람은 우승할 가능성이 없다. 자신이 최고의 점수를 받을 것이기 때문이다. 그러니 정렬한 배열에서 현재 인덱스보다 낮은 위치는 고려할 필요가 없다.

문제는 자기보다  높은 점수가 문제이다. 이 중에는 자신보다 높은 점수를 받는 사람이 있을 수 있다.

이것을 해결하기 위해서, maxarr이라는 배열을 만들었다. 이 배열은 마지막 라운드 이후에, i번째부터 마지막 점수까지의 최대 점수를 저장한 배열이다. 그렇기 때문에, 본인이 maxarr[i]보다 높거나 같으면 우승후보가 되는 것이다.

[ 그림 설명 ]

[ 코드 ]

// 1. 정렬
// 2. 뒤에서 부터 1씩 더한다. 높은 점수를 받은 놈일 수록 낮은 점수를 받아야한다.
// 3. i ~ N까지 최대값을 저장하는 배열(maxarr)을 만든다.
// 4. score[i] + N(i번째 얘가 받을 수 있는 최대)가 maxarr[i]보다 크면
// 우승후보자가 된다.
#include <iostream>
#include <algorithm>
using namespace std;
int T, tmpT, N;
int score[300001], maxarr[300001];
int main()
{
	cin >> T;
	tmpT = T;
	while (tmpT--)
	{
		cin >> N;
		for (int i = 0; i < N; i++)
			cin >> score[i];
		sort(score, score + N);
		int max_score = 0, final_score;
		for (int i = N - 1; i >= 0; i--)
		{
			final_score = score[i] + N - i;
			if (final_score > max_score)
				max_score = final_score;
			maxarr[i] = max_score;
		}
		int candidate = 0;
		for (int i = 0; i < N; i++)
		{
			if (score[i] + N >= maxarr[i])
				candidate++;
		}
		cout << "Case #" << T - tmpT << endl << candidate << endl;
	}
	return 0;
}