Computer Science/Algorithm Problem

백준] 2456 - 나는 학급회장이다(한국정보올림피아드:KOI 2011 지역본선)

TwinParadox 2019. 1. 23. 20:53
728x90

시간 제한 : 1초

메모리 제한 : 128MB




입력

첫째 줄에는 반의 학생들의 수 N (3<=N<=1,000)이 주어진다. 다음 N개의 각 줄에는 각 학생이 제출한 회장후보 3명에 대한 선호 점수가 주어지는 데, 첫 번째 점수는 후보 1번에 대한 점수이고 두 번째 점수는 후보 2번에 대한 점수이고 세 번째 점수는 후보 3번에 대한 점수이다. 이 세 점수는 서로 다르며, 1, 2, 3이 정확히 한 번씩 나타난다. 




출력

학생들의 선호도 투표 결과로부터, 회장이 유일하게 결정되는 경우에는 회장으로 결정된 후보의 번호와 최고 점수를 출력하고, 유일하게 결정할 수 없는 경우에는 0과 최고 점수를 출력한다.




소스코드

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
struct vote
{
	int one;
	int two;
	int three;
	int sum;
	int idx;
};
bool compare(const struct vote& a, const struct vote& b)
{
	if (a.sum > b.sum)
		return true;
	else
	{
		if (a.three > b.three)
			return true;
		else if (a.three == b.three)
		{
			if (a.two > b.two)
				return true;
			else
				return false;
		}
		else
			return false;
	}
}
int main(void)
{
	int n, tmp;
	cin >> n;
	vector<struct vote> arr(n, { 0,0,0,0,0 });
	for (int i = 0; i < 4; i++)
		arr[i].idx = i;
	
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= 3; j++)
		{
			cin >> tmp;
			if (tmp == 1)
				arr[j].one++;
			else if (tmp == 2)
				arr[j].two++;
			else
				arr[j].three++;
			arr[j].sum += tmp;
		}
	}
	sort(arr.begin(), arr.end(), compare);

	if (arr[0].sum == arr[1].sum)
	{
		if (arr[0].three == arr[1].three)
		{
			if (arr[0].two == arr[1].two)
				cout << "0" << " " << arr[0].sum;
			else if (arr[0].two > arr[1].two)
				cout << arr[0].idx << " " << arr[0].sum;
			else
				cout << arr[1].idx << " " << arr[1].sum;
		}
		else if (arr[0].three > arr[1].three)
		{
			cout << arr[0].idx << " " << arr[0].sum;
		}
		else
		{
			cout << arr[1].idx << " " << arr[1].sum;
		}
	}
	else
		cout << arr[0].idx << " " << arr[0].sum;
}




Tip

정렬 기준을 정해주면 풀 수 있다. 정렬 기준을 잘못 세워서 문제를 계속 틀렸던 게 함정...



728x90