[백준] 14889 스타트와 링크 C++ 문제 풀이

https://www.acmicpc.net/problem/14889

i와 j가 같은 팀일 때 더해지는 능력치 = S[i][j] + S[j][i]로 계산하며, 
두 팀의 능력치의 차이를 최소로 하고자 한다. 이를 구현하는 큰 원리는 아래와 같다.

(1) 모든 조합에 대해서 능력치의 차이를 구한다.
(2) 능력치의 차이가 최소인 경우, 그 값을 출력한다.

 

0 1 2 3 4 5
1 0 2 3 4 5
1 2 0 3 4 5
1 2 3 0 4 5
1 2 3 4 0 5
1 2 3 4 5 0
(1,3,6) 팀 = 1 + 2 + 5 + 1 + 3 + 5 = 17
(2,4,5) 팀 = 2 + 3 + 2 + 4 + 4 + 4 = 19

위와 같이, 3개의 팀원이 있다면 (1, 3) (1, 6) (3, 6) 세 개의 조합을 만들어 능력치를 계산하면 된다. 이때 (1, 3)과 (3, 1)은 같은 것이 아니므로 이중 for문을 돌려 구현한다. 

이 때, 최솟값을 구하기 위한 ret의 초기값(INF)은 능력치의 차이의 최댓값을 넣으면 된다. 한 팀은 능력치가 모두 0이라 가정하고, 나머지 팀의 최대 10명이 자신을 제외한 9명의 사람에 대해서 100만큼의 능력치를 모두 가지고 있다. 여기서 2를 곱해야하므로 최댓값은 18,000이 된다.

 

(참고) 시간초과 코드

#include <iostream>
#include <vector>
#include <cmath>
#include <algorithm>
#include <set>
using namespace std; 

int ability[21][21] = { 0, };
const int INF = 18001; 

// 현재 팀 구성에서의 능력치의 차이를 계산해 반환한다. 
int calc(vector<int> team, set<vector<int>> &visited) {
	vector<int> left, right; 
	vector<int>::iterator middle(team.begin() + team.size() / 2); 

	// 스타트팀과 링크팀으로 분할
	for (auto it = team.begin(); it != team.end(); it++) {
		if (distance(it, middle) > 0) 
			left.push_back(*it);
		else
			right.push_back(*it); 
	}

	// 이미 검사한 조합인지 검사
	if (visited.find(left) != visited.end() || visited.find(right) != visited.end()) return INF; 

	// 검사하지 않은 조합이면 visited에 추가
	visited.insert(left); visited.insert(right); 

	int sumLeft = 0, sumRight = 0; 
	// 스타트팀 능력치 계산
	for (int i : left) for (int j : left) 
		sumLeft += ability[i][j];

	// 링크팀 능력치 계산
	for (int i : right) for (int j : right)
		sumRight += ability[i][j];

	return abs(sumLeft - sumRight); 
}

int main() {
	int n; cin >> n; 
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			cin >> ability[i][j]; 
	vector<int>	team; 
	for (int i = 0; i < n; i++)
		team.push_back(i); // 0부터 n-1까지 선수를 저장

	set<vector<int>> visited; 
	int ret = INF; 
	do {
		int cand = calc(team, visited); 
		if (ret > cand) ret = cand; 
	} while (next_permutation(team.begin(), team.end())); 
	
	cout << ret << endl;
	return 0; 
}

스타트팀의 조합이 만들어지면 링크팀의 조합도 자연스레 만들어진다.
1. 1부터 N까지의 순열을 만들어 절반의 왼쪽은 스타트, 오른쪽은 링크팀으로 한다. 
2. 순서는 상관없으니 같은 조합이 만들어지면 연산을 생략한다.
3. 능력치 차이가 최소인 경우를 찾아낸다.

이 설계는 next_permutation의 인자로 최대 20의 사이즈인 team이 들어간다는 점에서 시간 복잡도가 엄청 늘어난다는 단점이 있었다. 

 20개에서 10개를 뽑는 조합을 먼저 구현하면 그 나머지를 다른 팀으로 두면 된다. 이 경우에는 모든 순열을 다 검사하는 것이 아니라 절반으로 나누는 조합 20C10만 계산하면 된다. 따라서 팀을 나누는 과정의 시간복잡도는 20!에서 184756으로 떨어진다.

team의 내부 요소들을 N/2개의 0과 1로만 배치하여 next_permutation을 사용한다. 이렇게 단순하게 표현된 배열을 순회하면 0부터 N까지의 순열을 만드는 것보다 훨씬 시간복잡도가 줄어든다. 

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

int ability[21][21];
const int INF = 18001;

int main() {
	int n; cin >> n; 
	for (int i = 0; i < n; i++)
		for (int j = 0; j < n; j++)
			cin >> ability[i][j]; 

	vector<int> binary(n);  // 0으로 n개 채워져있음
	for (int i = n / 2; i < n; i++)
		binary[i] = 1; 

	int ret = INF; 
	do {
		vector<int> left, right; 
		for (int i = 0; i < n; i++) {
			if (binary[i] == 0) // 스타트팀이면
				left.push_back(i);
			else
				right.push_back(i); // 링크팀이면
		}

		int leftSum = 0, rightSum = 0; 
		for (int i : left) for (int j : left)
			leftSum += ability[i][j];
		for (int i : right) for (int j : right)
			rightSum += ability[i][j];

		int cand = abs(leftSum - rightSum); 
		if (ret > cand) ret = cand; 
	} while (next_permutation(binary.begin(), binary.end()));

	cout << ret << endl;
	return 0; 
}