Computer Science/Algorithm Problem

백준] 2303 - 숫자 게임(한국정보올림피아드 2005;KOI 2005 초등부)

TwinParadox 2019. 4. 14. 08:04
728x90

시간 제한 : 2초
메모리 제한 : 128MB

 


입력

첫 줄에는 사람의 수를 나타내는 정수 N이 주어진다. N은 2이상 1,000이하이다. 그 다음 N 줄에는 1번부터 N번까지 각 사람이 가진 카드가 주어지는 데, 각 줄에는 1부터 10사이의 정수가 다섯 개씩 주어진다. 각 정수 사이에는 한 개의 빈칸이 있다.

 


출력

게임에서 이긴 사람의 번호를 첫 번째 줄에 출력한다. 이긴 사람이 두 명 이상일 경우에는 번호가 가장 큰 사람의 번호를 출력한다.

 


소스코드

#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;
struct user
{
	vector<int> card;
	int su;
	int idx;
};
bool compare(const struct user a, const struct user b)
{
	if (a.su > b.su)
		return true;
	else if (a.su == b.su)
		return a.idx > b.idx;
	else
		return false;
}
int main(void)
{
	int N, deckSize = 5;
	cin >> N;
	
	vector<struct user> arr(N, { vector<int>(deckSize),0,0 });
	for (int i = 0; i < N; i++)
	{
		int tmp;
		for (int j = 0; j < deckSize; j++)
		{
			cin >> tmp;
			arr[i].card[j] = tmp;
			arr[i].idx = i + 1;
		}
	}

	for (int i = 0; i < N; i++)
	{
		for (int first = 0; first < deckSize; first++)
		{
			if (arr[i].su == 9)
				break;
			for (int second = first + 1; second < deckSize; second++)
			{
				if (arr[i].su == 9)
					break;
				for (int third = second + 1; third < deckSize; third++)
				{
					int sum = arr[i].card[first] + arr[i].card[second] + arr[i].card[third];
					if (arr[i].su < (sum % 10))
						arr[i].su = (sum % 10);
					if (arr[i].su == 9)
						break;
				}
			}
		}
	}

	sort(arr.begin(), arr.end(), compare);
	cout << arr[0].idx;
}

 


Tip

무식하게 모든 경우를 찾아서 정답을 구해내면 되는 문제다.

 

728x90