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

 처음에 스타트와 링크를 풀어놓고는 다른문제인 링크와 스타트에 제출을 하고 있었다. 레전드

백트래킹을 통한 완전탐색문제이다. N도 최대 20이라 시간에 딱히 신경을 안쓰고 구현에 집중하면 풀 수 있는 문제다.

 

1. N까지 N / 2 개의 조합을 구한다. 여기서 조합에 선택된 팀1과 선택되지 않은 팀2로 나뉜다.

2. 팀1의 능력치와 팀2의 능력치를 구해 최솟값을 갱신한다.

3. 모든 조합을 구할 때 까지 반복한다.

 

	#include <iostream>
	#include <vector>
	#include <climits>
	#define MAX 20
	using namespace std;
	int N;
	int board[MAX][MAX];
	bool check[MAX] = { false, };
	int answer = INT_MAX;
	void sol() {
		int team1 = 0;
		int team2 = 0;

		for (int i = 0; i < N; i++) {
			for (int j = i + 1; j < N; j++) {
				if (check[i] && check[j])
					team1 += board[i][j] + board[j][i];
				else if (!check[i] && !check[j])
					team2 += board[i][j] + board[j][i];
			}
		}

		answer = min(answer, abs(team1 - team2));
		if (answer == 0) {
			cout << "0" << '\n';
			exit(0);
		}
	}

	void combination(int idx, int cnt) {
		if (cnt == N / 2) {
			sol();

			return;
		}

		for (int i = idx; i < N; i++) {
			if (check[i] == true) continue;

			check[i] = true;
			combination(i, cnt + 1);
			check[i] = false;
		}
	}

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

		combination(0, 0);

		cout << answer << '\n';

		return 0;
	}