백준 알고리즘 14889번: 스타트와 링크 [C++]

문제 출처: www.acmicpc.net/problem/14889

14889번: 스타트와 링크

1. 코드

#include <iostream>
#include <vector>
#include <cmath>

using namespace std;

int board[21][21] = { 0, };		//능력치 저장 보드
int board_size;				//보드의 크기
int low = 100;				//제일 적은 오차의 크기
int flag[21] = { 0, };			//해당 인원의 소속 여부 확인용
vector <int> start;			//start팀의 구성
vector <int> link;			//link팀의 구성

void team(int a, int d)			//팀 선정 후 능력치 차이 확인
{
	if (a == board_size / 2)	//link팀 선정 후 능력치 차이 확인
	{
		int S = 0;		//start팀의 총 능력치
		int L = 0;		//link팀의 총 능력치

		for (int i = 1; i <= board_size; i++)
		{
			if (!flag[i]) link.push_back(i);	//팀에 소속하지않은 인원들을 link에 소속시키기
		}

		for (int i = 0; i < board_size / 2; i++)
		{
			for (int j = 0; j < board_size / 2; j++)
			{
				S += board[start[i]][start[j]];		//start팀의 능력치 점수
				L += board[link[i]][link[j]];		//linck팀의 능력치 점수
			}
		}
		
		if (abs(S - L) < low)		//능력치 점수의 차이
			low = abs(S - L);
		
		if (!low)	//low값이 0이면 더이상 능력치 점수의 차이가 발생하지않는다는 것이기에 프로그램 종료
		{
			cout << low;
			exit(0);
		}
		
		link.clear();	//link 벡터 전체 초기화
		return;
	}

	for (int i = d; i <= board_size; i++)	//start팀만 소속 진행
	{
		if (flag[i]) continue;		//팀에 소속된 인원 제외

		flag[i] = true;			//팀에 소속됨
		start.push_back(i);		//start팀에 소속

		team(a + 1, i + 1);
		
		start.pop_back();		//다른 인원 소속을 위해 제외
		flag[i] = false;		//팀에 소속이 안됨
	}
}

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> board_size;

	for (int i = 1; i <= board_size; i++)
	{
		for (int j = 1; j <= board_size; j++)
		{
			cin >> board[i][j];
		}
	}
	team(0, 1);
	cout << low;
	return 0;
}

(실행)

2. 풀이

문제는 vector와 재귀를 이용하여 문제를 해결하였다.

int board[21][21] = { 0, };		//능력치 저장 보드
int board_size;				//보드의 크기
int low = 100;				//제일 적은 오차의 크기
int flag[21] = { 0, };			//해당 인원의 소속 여부 확인용
vector <int> start;			//start팀의 구성
vector <int> link;			//link팀의 구성

문제 해결에 필요한 요소들을 정의한다.

int main(void)
{
	ios::sync_with_stdio(false);
	cin.tie(NULL);
	cin >> board_size;

	for (int i = 1; i <= board_size; i++)
	{
		for (int j = 1; j <= board_size; j++)
		{
			cin >> board[i][j];
		}
	}
	team(0, 1);
	cout << low;
	return 0;
}

그리고 사용자에게 입력값을 받는데 board 같은 경우 문제를 조금 편하게 풀기위해 (1, 1)부터 입력을 받는다. team 함수를 실행을 한다.

void team(int a, int d)			//팀 선정 후 능력치 차이 확인
{
	if (a == board_size / 2)	//link팀 선정 후 능력치 차이 확인
	{
		int S = 0;		//start팀의 총 능력치
		int L = 0;		//link팀의 총 능력치

		for (int i = 1; i <= board_size; i++)
		{
			if (!flag[i]) link.push_back(i);	//팀에 소속하지않은 인원들을 link에 소속시키기
		}

team 함수에서는 팀을 선정하는 작업과 각 팀의 능력치를 구하고 팀의 능력치 차이를 구하는 함수이다. 먼저 a가 board_size와 같은 경우라면 이미 start팀의 팀원들은 이미 선정이 되어있고, link팀의 팀원들은 선정이 안된 상태이다. 그렇기에 flag를 통해 팀에 소속하지않은 인원들을 link에 소속시킨다.

for (int i = 0; i < board_size / 2; i++)
{
	for (int j = 0; j < board_size / 2; j++)
	{
		S += board[start[i]][start[j]];		//start팀의 능력치 점수
		L += board[link[i]][link[j]];		//linck팀의 능력치 점수
	}
}

그리고 각 팀의 능력치 점수의 총합을 구한다.

if (abs(S - L) < low)		//능력치 점수의 차이
	low = abs(S - L);
		
if (!low)	//low값이 0이면 더이상 능력치 점수의 차이가 발생하지않는다는 것이기에 프로그램 종료
{
	cout << low;
	exit(0);
}
		
link.clear();	//link 벡터 전체 초기화
return;
}

그리고 abs를 이용하여 팀의 능력치 차이의 크기를 구하며 그 크기가 low보다 작다면 low값으로 초기화한다. 그런데 low값이 0이라면 더이상 능력치 차이가 줄어들지않기 때문에 프로그램을 종료한다. 종료하지않으면 다른 경우의 수를 탐색하기 때문이다. 그리고 link팀은 a == board_size / 2에서만 팀을 선언하기 때문에 link를 전체 초기화 시켜준다. 그리고 반환을 하여 다른 경우의 수를 탐색한다.

for (int i = d; i <= board_size; i++)	//start팀만 소속 진행
{
	if (flag[i]) continue;		//팀에 소속된 인원 제외

	flag[i] = true;			//팀에 소속됨
	start.push_back(i);		//start팀에 소속

	team(a + 1, i + 1);
		
	start.pop_back();		//다른 인원 소속을 위해 제외
	flag[i] = false;		//팀에 소속이 안됨
}

a == board_size / 2가 아닐 경우 start 팀의 팀원 선정을 진행하는데 flag를 이용하여 해당인원이 팀에 소속되어있는지 확인해주고, 안되어있다면 start팀에 소속과 동시에 소속되었다는 것을 표시한다. 그리고 재귀 함수를 호출 후 종료가 된 후 다른 경우의 수를 찾기 위해 start팀의 해당 인원을 제외시키고 팀에 소속되어있지않음을 표시한다.

정리하면 start팀을 우선적으로 선정을 한 뒤에 link팀을 선정한다. 그리고 팀의 능력치 합을 구한 뒤 팀의 능력 차이의 크기가 제일 작은 것을 저장한 뒤 그것을 출력하는 것이다.

3. 느낀 점

문제 자체는 어려운 문제가 아니였지만 시간 초과 에러가 계속해서 나와 경우의 수를 줄이는 것이 상당히 힘들었다. 결국 경우의 수를 제외하는 부분을 다른 코드를 검색해서 알아내어 해결했지만 다음에는 스스로의 힘으로 풀도록 노력해야겠다.