[백준 2303] 숫자 게임

문제출처: https://www.acmicpc.net/problem/2303

문제

N명이 모여 숫자 게임을 하고자 한다. 각 사람에게는 1부터 10사이의 수가 적혀진 다섯 장의 카드가 주어진다. 그 중 세 장의 카드를 골라 합을 구한 후 일의 자리 수가 가장 큰 사람이 게임을 이기게 된다. 세 장의 카드가 (7, 8, 10)인 경우에는 합은 7+8+10 = 25가 되고 일의 자리 수는 5가 된다. 어떤 사람이 받은 카드가 (7, 5, 5, 4, 9)인 경우 (7, 4, 9)를 선택하면 합이 20이 되어 일의 자리 수는 0이 되고, (5, 5, 9)를 선택하면 합이 19가 되어 일의 자리 수는 9가 된다. 게임을 이기기 위해서는 세 장의 카드를 선택할 때 그 합의 일의 자리 수가 가장 크게 되도록 선택하여야 한다.

예를 들어, N=3일 때

• 1번 사람이 (7, 5, 5, 4, 9),
• 2번 사람이 (1, 1, 1, 1, 1),
• 3번 사람이 (2, 3, 3, 2, 10)의 

카드들을 받았을 경우, 세 수의 합에서 일의 자리 수가 가장 크게 되도록 세 수를 선택하면

• 1번 사람은 (5, 5, 9)에서 9,
• 2번 사람은 (1, 1, 1)에서 3,
• 3번 사람은 (2, 3, 3)에서 8의

결과를 각각 얻을 수 있으므로 첫 번째 사람이 이 게임을 이기게 된다.

N명에게 각각 다섯 장의 카드가 주어졌을 때, 세 장의 카드를 골라 합을 구한 후 일의 자리 수가 가장 큰 사람을 찾는 프로그램을 작성하시오. 가장 큰 수를 갖는 사람이 두 명 이상일 경우에는 번호가 가장 큰 사람의 번호를 출력한다.

입력

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

출력

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

풀이

구현문제를 풀 때 마다 항상 느끼는건데 어려운 자료구조,알고리즘이 들어가있지않은 문제를 푸는데도 코딩하는데 어려움을 느끼는 저의 무능함을 반성하게됩니다..(거의 1년 째 되가는데도...)

이 문제에서 중요한 건 20~33행에 이르는 4중 반복문을 구현할 수 있느냐입니다. 모든 경우를 따져야 하므로 22~26행처럼 작성해야 각각의 인원들이 갖고있는 5개의 카드의 자릿수의 최고3조합을 따져볼 수 있습니다. 이 때 큰숫자3개의조합이 가장큰 일의자리를 갖는게 아니므로 각각의카드값들을 정렬할 필요는없습니다. 그리고 각각의 인원별로 자릿수가 최대인 값을 저장해둡니다. 그리고 32행을 살펴보면 각 인원의 최고자릿수값을 저장해둠과 별개로 35행의 비교연산을 위해 전체의 최대값을 구해놓습니다. 마지막으로 배열에 저장해둔 값을 최고값과 비교하며 그때의 index를 출력합니다.

**소스코드의 주석을 보면 이해가 갈겁니다.

코드

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int arr[1000][5];
int score[1000];
int main()
{
	int n;
	cin >> n;
	vector<int>v;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < 5; j++)
		{
			cin >> arr[i][j];
		}
	}
	//최대값을 구하자
	int max_value = 0;
	//각 인원의 최대값을 구하기위해 22행수행
	for (int i = 0; i < n; i++)
	{
		//5개 카드중 3개조합으로 최대값구하기
		for (int j = 0; j < 5; j++)
		{
			for (int k = j + 1; k < 5; k++)
			{
				for (int l = k + 1; l < 5; l++)
				{
					//각 인원의 최대값 저장
					score[i] = max(score[i], (arr[i][j] + arr[i][k] + arr[i][l]) % 10);
				}
			}
		}
		//비교연산을 위해 전체 최대값저장
		max_value = max(max_value, score[i]);
	}
	int index = 0;
	//각 인원의 값과 비교해가며 최대값일 때 index출력
	for (int i = 0; i < n; i++)
	{
		if (score[i] == max_value)
			index = i + 1;
	}
	cout << index << endl;
}

결과