[백준 14889] 스타트와 링크

두 팀으로 나누기만 하면 되는 문제다.

스타트 팀이 될 사람만 체크하고, 스타트 팀과 링크 팀이 완성되면 두 팀의 전력차를 계산하자.

 

여기서, 한가지 재미있는 점은 4명이 있다고 가정했을 때,

1. 스타트 팀 : (0 ,1), 링크 팀 : (2, 3)
2. 스타트 팀 : (2, 3), 링크 팀 : (0, 1)

이 두 가지 경우는 사실상 같은 경우이다.

왜냐하면, (0, 1)이 스타트 팀인지 링크 팀인지 상관없다. 그냥 (0, 1)이 같은 팀이기만 하면 되기 때문이다.

이 사실을 이용하면 시간 복잡도를 줄일 수 있다.

 

1. naive하게 구현

#include <bits/stdc++.h>
using namespace std;

const int INF = 2147483647;

int n;
bool isStartTeam[21]; // 어떤 사람이 스타트 팀이지 체크
int sTeam[21], lTeam[21]; // 각 팀의 팀원 목록
int power[21][21]; // 능력치 저장
int ans = INF; // 답

// cur은 몇번부터 뽑을 차례인지, cnt은 몇명을 뽑았는지
void recur(int cur, int cnt) {

	if (cnt == n / 2) {
		int curStart = 0, curLine = 0;
		// 스타트팀과 링크팀을 나눔.
		for (int i = 0; i < n; ++i) {
			if (isStartTeam[i]) sTeam[curStart++] = i;
			else lTeam[curLine++] = i;
		}
		// 전력 계산
		int sPower = 0, lPower = 0;
		for (int i = 0; i < n / 2; ++i) for (int j = 0; j < n / 2; ++j) {
			sPower += power[sTeam[i]][sTeam[j]];
			lPower += power[lTeam[i]][lTeam[j]];
		}
		
		// 답 갱신
		ans = min(ans, abs(sPower - lPower));
		
		return;
	}

	for (int i = cur; i < n; ++i) {
		isStartTeam[i] = true;
		
		recur(i + 1, cnt + 1);

		isStartTeam[i] = false;
	}
}


int main() {
	ios::ios_base::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 >> power[i][j];

	recur(0, 0);

	cout << ans;
	return 0;
}

 

2. 같은 경우를 제거

#include <bits/stdc++.h>
using namespace std;
const int INF = 2147483647;

int n;
bool isStartTeam[21];
int sTeam[21], lTeam[21];
int power[21][21];
int ans = INF;

void recur(int cur, int cnt) {

	if (cnt == n / 2) {
		int curStart = 0, curLine = 0;

		for (int i = 0; i < n; ++i) {
			if (isStartTeam[i]) sTeam[curStart++] = i;
			else lTeam[curLine++] = i;
		}

		int sPower = 0, lPower = 0;
		for (int i = 0; i < n / 2; ++i) for (int j = 0; j < n / 2; ++j) {
			sPower += power[sTeam[i]][sTeam[j]];
			lPower += power[lTeam[i]][lTeam[j]];
		}

		ans = min(ans, abs(sPower - lPower));

		return;
	}
	
	// for문의 범위가 바뀜
	for (int i = cur; i < n / 2 + cnt; ++i) {
		isStartTeam[i] = true;

		recur(i + 1, cnt + 1);

		isStartTeam[i] = false;
	}
}


int main() {
	ios::ios_base::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 >> power[i][j];

	recur(0, 0);

	cout << ans;
	return 0;
}

확실히 빨라졌다.