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

https://tigerfrom2.tistory.com/80 스타트와 링크에서 파생된 문제이다.

스타트와 링크에서는 반드시 3대3 혹은 2대2 처럼 같은 인원수만큼의 팀원들이 있었지만 여기선 1대5, 2대4가 가능하다.

처음에 스타트와 링크를 풀어놓고 제출을 이 문제에 해서 정답률이 처참하다...

 

 1~N까지 조합의 수를 확인해야한다. 반복문을 하나 추가하는 것 외에 스타트와 링크 문제와 다른 것은 거의없다.

 

	#include <iostream>
	#include <vector>
	#include <climits>
	#define MAX 20
	using namespace std;
	int N;
	int board[MAX][MAX];
	bool check[MAX];
	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, int num) {
		if (cnt == num) {
			sol();

			return;
		}

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

			check[i] = true;
			combination(i, cnt + 1, num);
			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];
			}
		}
		for (int i = 0; i < MAX; i++)
			check[i] = false;

		for(int i = 0; i < N; i++)
		combination(0, 0, i);

		cout << answer << '\n';

		return 0;
	}