[백준] C++ 스타트와 링크(14889)

이 문제는 조합을 이용하는 문제이다. 모든 경우의 수를 확인해서 차이가 최소인 값을 출력하면 된다.

1, 2, 3, 4가 있으면 (1,2 / 3,4), (1,3 / 2,4), (1,4 / 2,3)  이 경우에 대해서만 확인을 하면 된다.

 

문제해결방법

1. 모든 경우의 조합에 대해 확인한다. (6명이 있으면 3명만 뽑는다. 나머지 3명은 남는 사람으로 따로 계산)

2. 스타트 팀과 링크팀의 차이를 구한다.(abs(스타트-링크))

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

void DFS(int size, int count, int start);

vector<int>v[1000];
int visited[1000];
int result = 987654321;

int main(void)
{
	int N = 0;


	cin >> N;
	int num = 0;
	for (int i = 0; i < N; i++)
	{
		for (int j = 0; j < N; j++)
		{
			cin >> num;
			v[i].push_back(num);
		}
	}

	DFS(v[0].size(), 0, 0);

	cout << result;
	return 0;
}

void DFS(int size, int count, int start)
{
	if (count == size / 2)//만약 절반만큼 인원을 뽑았다면 이제는 계산을 하자
	{
		int num1 = 0;
		for (int i = 0; i < size; i++)//스타트팀 계산
		{
			if (visited[i] == 1)
			{
				for (int j = 0; j < size; j++)
				{
					if (i != j && visited[j] == 1)
					{
						num1 += v[i][j];
					}
				}
			}
		}

		int num2 = 0;
		for (int i = 0; i < size; i++)//링크팀 계산
		{
			if (visited[i] == 0)
			{
				for (int j = 0; j < size; j++)
				{
					if (i != j && visited[j] == 0)
					{
						num2 += v[i][j];
					}
				}
			}
		}
		int sum = abs(num1 - num2);
		if (sum < result)
		{
			result = sum;
		}
	}
	else
	{
		for (int i = start; i < size; i++)// 인원을 뽑는다.(중복 방지를 위해 start를 사용)
		{
			if (visited[i] == 0)
			{
				visited[i] = 1;
				DFS(size, count + 1, i);
				visited[i] = 0;
			}
		}
	}
}

 

생각보다 어렵지 않은 문제이다. 모든 경우의 수를 DFS로 확인하면서 차이가 최소가 되는 값을 찾으면 된다.