알고리즘 :: 백준 :: Bruteforce :: 14889 :: 스타트와 링크

문제

문제링크
축구를 하기 위해 모인 사람은 총 N명이고 신기하게도 N은 짝수이다. 이제 N/2명으로 이루어진 스타트 팀과 링크 팀으로 사람들을 나눠야 한다. 사람에게 번호를 1부터 N까지로 배정했고, 아래와 같은 능력치를 조사했다. 능력치 Sij는 i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치이다. 팀의 능력치는 팀에 속한 모든 쌍의 능력치 Sij의 합이다. Sij는 Sji와 다를 수도 있으며, i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치는 Sij와 Sji이다. 축구를 재미있게 하기 위해서 스타트 팀의 능력치와 링크 팀의 능력치의 차이를 최소로 하려고 한다. 첫째 줄에 스타트 팀과 링크 팀의 능력치의 차이의 최솟값을 출력한다.

문제접근

• N은 20까지이므로 임의의 한 사람을 스타트팀에 넣기 or 링크팀에 넣기로 구분한다면 $O(2^n)$으로 해결할 수 있다.
• 이정도면 bruteforce로 해결할 수 있는데, 구체적으로는 bruteforce 중에서도 두 가지 방법으로 풀 수 있다.
  1. 재귀를 사용하는 백트래킹 방법
  2. 조합을 사용하는 forwarding 방법
  • 두 방법 모두 bruteforce를 넘어 전체적인 PS의 풀이 흐름에서 정말 중요하다!

백트래킹 방법 (재귀)

• idx번째 사람을 스타트팀에 넣는 경우 or 링크팀에 넣는 경우 각각 구분해서 재귀를 돌리는 방법이다.
• 백트래킹이므로 적절한 조건을 세워야 한다. 문제에 따라 스타트팀의 인원 또는 링크팀의 인원이 $n/2$를 넘는 경우 해당 경우의 수는 존재할 수 없는 경우이므로 return 한다.
• Bruteforce의 대원칙 고정/ 실행/ 해제는 여기서도 적용되므로 꼭 잊지말고 어느 팀에 넣어준 뒤 재귀를 돌리고 해제해주자.

조합(combination) 방법 (비재귀)

• 선수를 1부터 N까지의 숫자라고 생각해보자.
• 우리는 각 팀에서 $N/2$ 명씩 선택하면 되는 것이다.
• 선택은 곧 중복을 허용하지 않는 순열, 즉, 조합이다.
• 조합은 <algorithm>헤더의 next_permutation() 함수를 사용하는데, 순열 조합은 거의 $O(n!)$ 알고리즘이므로 사용할 때는 최대한 신경을 많이 써줘야 한다.
  1. N의 범위에 신경을 많이 써주자. N = 20이지만 사실 우리는 $N/2$ 명을 뽑으면 나머지 인원은 다른 팀에 넣으면 되기 때문에 이 방법을 사용할 수 있다.
  2. 생각해보면 1, 2 | 3, 4 이렇게 팀을 맺는것과 2, 1 | 3, 4는 같은 결과다. 나열해보면, 4명에서 나올 수 있는 순열은 4! = 24가지지만, 유효한 조합은 1, 2 | 3, 4, 1, 3 | 2, 4, 1, 4 | 2, 3 이렇게 3가지 뿐이다. 따라서 첫 번째 숫자를 고정시켜버리고 n - 1개 숫자에 대해서만 조합을 신경써주면 된다. 이러면 계산효율이 n배 증가하므로 매우매우 좋은 착안점이다.

코드

백트래킹 방법 (재귀) 코드

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

int N;
int stat[20][20];
vector<int> teamStart, teamLink;

int solve(int idx) {
	// 백트래킹 사용: 재귀를 돌다가 불가능한 경우를 만날 경우 해당 재귀를 멈춘다.
	if (teamStart.size() > N / 2 || teamLink.size() > N / 2) return -1;
	if (idx == N) {		// 모든 사람을 각 팀에 배분했다. 
		int statSumOfStart = 0, statSumOfLink = 0;
		for (int i = 0; i < N / 2; ++i) {
			for (int j = 0; j < N / 2; ++j) {
				if (i == j) continue;
				statSumOfStart += stat[teamStart[i]][teamStart[j]];
				statSumOfLink += stat[teamLink[i]][teamLink[j]];
			}
		}
		return abs(statSumOfStart - statSumOfLink);
	}

	int ret = -1, temp = -1;
	// idx번째 선수를 'Start팀'에 넣는 경우
	teamStart.push_back(idx);
	temp = solve(idx + 1);
	if (ret == -1 || (temp != -1 && ret > temp)) ret = temp;
	teamStart.pop_back();
	// idx번째 선수를 'Link팀'에 넣는 경우
	teamLink.push_back(idx);
	temp = solve(idx + 1);
	if (ret == -1 || (temp != -1 && ret > temp)) ret = temp;
	teamLink.pop_back();

	return ret;
}

int main() {
	ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
	cin >> N;
	for (int i = 0; i < N; ++i) 
		for (int j = 0; j < N; ++j) 
			cin >> stat[i][j];
	cout << solve(0) << '\n';
}

조합 방법 (비재귀) 코드

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

int main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int n;
	cin >> n;
	int score[n][n];
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < n; ++j)
			cin >> score[i][j];
	
	int ans = 1e9;
	char check[n];
	// The number of people in each team can be from 1 to n-1.
	for (int part = 1; part <= n - 1; ++part) {
		// initialize check array for permutation(or selection).
		for (int i = 0; i < part; ++i) check[i] = 0;
		for (int i = part; i < n; ++i) check[i] = 1;
		int counterPart = n - part;
		int teamS[part], teamL[counterPart];
		do {
	        // devide team by permutation.
			for (int i = 0, l = 0, r = 0; i < n; ++i)
				(check[i]) ? teamL[r++] = i : teamS[l++] = i; 
			// get score sum of each team.
	        	int sumS = 0, sumL = 0;
	        	for (int i = 0; i < part; ++i)
	        		for (int j = i + 1; j < part; ++j)
					sumS += score[teamS[i]][teamS[j]] + score[teamS[j]][teamS[i]];
			for (int i = 0; i < counterPart; ++i)
				for (int j = i + 1; j < counterPart; ++j)
					sumL += score[teamL[i]][teamL[j]] + score[teamL[j]][teamL[i]];
			ans = min(ans, abs(sumS - sumL));		
		} while(next_permutation(check + 1, check + n)); // for increase calc speed!
	}
	cout << ans << '\n';
}

결과

백트래킹

조합