[백준/c++] BOJ 14889 - 스타트와 링크

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

14889번: 스타트와 링크

 

문제 설명

N명의 사람을 N/2명씩 나누어 두 팀을 구성한다.

능력치 표가 주어지며, Sij는 i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치이다.

두 팀의 능력치의 차이의 최솟값을 출력해라.

N(4 <= N <= 20, N은 짝수), Sij (1 <= Sij <= 100)

 

 

해결

사람들의 조합을 짜기 위해 dfs를 이용한다.

team[21] -> 1이면 start, 0이면 link 팀으로 들어감

 

1. dfs 종료

- cnt가 N / 2가 되면 종료 (사람의 반이 start 팀으로 들어간 것)

- team배열에 저장된 대로  a, b에 각각 능력치를 저장함

- ans 보다 차이가 작다면 ans에 저장

 

2. 조합

- idx부터 n까지 돌면서 오름차순으로 조합 선택

- solve 함수를 호출하기 전, 해당 idx의 team을 1로 바꿔 줌 / 호출 후 다시 0으로 변경

 

 

코드

#include<bits/stdc++.h>
#define x first
#define y second
using namespace std;

int n;
int arr[21][21], team[21];
int ans = 987654321;

void solve(int cnt, int idx) {
	if (cnt == n / 2) {
		int a = 0, b = 0;

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				if (team[i] && team[j]) a += arr[i][j];
				else if (!team[i] && !team[j]) b += arr[i][j];
			}
		}

		ans = min(ans, abs(a - b));
		return;
	}

	for (int i = idx; i < n; i++) {
		if (team[i]) continue;
		team[i] = 1;
		solve(cnt + 1, i + 1);
		team[i] = 0;
	}
}

int main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);

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

	solve(0, 0);
	cout << ans;
}