(C++) 백준 2456 - 나는 학급회장이다.

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

문제

> N명의 학생이 3명의 후보로 회장선거를 하려고한다.
> 각 학생은 후보의 선호도에 따라 3점, 2점, 1점을 주어야한다.
> 후보의 최종 점수는 각 학생의 선호도를 모두 더한 값이고 가장 큰 점수를 받으면 당선된다. 만약 동점이라면 3점이 더 많은 후보, 2점이 더많은 후보가 당선이다. 만약 둘다 같다면 회장이 결정되지 않는다.
> 회장이 결정되면 번호와 점수를 출력하고 결정되지 못하면 0번과 최고 점수를 출력해라.

접근

각 후보에 대해 3점, 2점, 1점에 대해서 따로 받은 득표수를 누적한다.
득표수를 이용해 먼저 총 점수를 계산해 구하고 동점자여부를 확인한다.
동점자여부에 따라 누적했던 각 득표수를 기준으로 문제에 조건에 맞게 비교한다.

문제해결

> 이차원벡터로 후보자의 번호와 점수를 인덱스로해 득표수를 누적한다. 후보는 0번이 없으므로 1번 인덱스부터 하기위해 범위와 반복문의 범위를 조정하였다.
> 각 후보의 점수를 계산한다. 득표수에 해당하는 인덱스가 각 점수이므로 득표수*인덱스하여 총 합을 구한다.
> 가장 큰 점수를 구하고 후보자의 점수와 비교해 점수벡터 rst에 넣는다. rst의 크기가 1이면 단독이므로 출력하고 종료한다.
> 1이상이면 동점자가 있으므로 문제 조건에 맞게 각 점수별 득표수로 비교한다. 모든 동점자 후보들의 비교가 끝나고 전부 동점일때의 valid값이 true면 0을, 아니면 최종 당선자를 출력한다.

코드

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

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);

	int N;
	cin >> N;
	vector<vector<int>> cdt(4, vector<int>(N + 2, 0));
	vector<int> sum(4, 0);
	for (int i = 1; i <= N; i++)
	{
		for (int j = 1; j <= 3; j++)
		{
			int tmp;
			cin >> tmp;
			cdt[j][tmp]++;
		}
	}
	for (int i = 1; i <= 3; i++)
		for (int j = 1; j <= 3; j++) sum[i] += cdt[i][j] * j;

	int select = max({ sum[1], sum[2], sum[3] });
	vector<int>rst;
	for (int i = 1; i <= 3; i++)
	{
		if (sum[i] == select)
		{
			rst.push_back(i);
		}
	}

	if (rst.size() == 1)
	{
		cout << rst[0] << " " << select << '\n';
		return 0;
	}

	int best = rst[0];
	bool valid = false;
	for (int i = 1; i < rst.size(); i++)
	{
		if (cdt[best][3] < cdt[rst[i]][3])
		{
			best = rst[i];
			valid = false;
		}
		else if (cdt[best][3] == cdt[rst[i]][3])
		{
			if (cdt[best][2] < cdt[rst[i]][2])
			{
				best = rst[i];
				valid = false;
			}
			else if (cdt[best][2] == cdt[rst[i]][2]) valid = true;
		}
	}
	cout << (valid ? 0 : best) << " " << select << '\n';
}

후기

후보자의 인덱스, 점수의 인덱스 처리에 자주 헷갈려 고생했다. 더 간결하게 처리하는 법을 연구해보자.
마지막 동접자 비교에서 모든 후보를 비교하지않고 중간에 최종자가 나오거나 2점까지 동일한 후보가 나오면 끝내도록해서 계속 틀렸다. 로직을 더 견고하게 만들어보자.