[C++] 백준 14889. 스타트와 링크

🌽 문제

🥕 입출력

🥔 풀이

절반의 조합을 고르는 것까진 dfs로 어떻게 해보겠는데
고른 것들의 스킬합을 구하는 방법을 생각하는 데에서 애를 먹었다.
풀고 나니 별 거 아녔다.

N은 짝수이므로 고른 것(used)의 갯수가 전체의 절반이 되면
자동으로 고르지 않은 것이 나머지 팀의 조합이라고 생각하면 된다.

dfs문에서 스킬합을 구하는 부분의 for문을 아래와 같이 작성했다가
자꾸 시간 초과가 떠서 절반만 살펴보도록 수정하여 해결했다.

for (int i = 0; i < n; i++) {
	for (int j = i + 1; j < n; j++) {
    	if (i == j) continue;
        // ...
    }
}

아래 else문도 else {link += arr[i][j] + arr[j][i]}; 로 썼다가 고쳤다.
주의!

else if (!used[i] && !used[j]) link += arr[i][j] + arr[j][i];

🥬 코드

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

int n;
int arr[20][20];
bool used[20];
int diff = 2e9;

void dfs(int now, int cnt) {
	if (cnt == n / 2) {
		int star = 0, link = 0;
		for (int i = 0; i < n; i++) {
			for (int j = i + 1; j < n; j++) {
				if (used[i] && used[j]) star += arr[i][j] + arr[j][i];
				else if (!used[i] && !used[j]) link += arr[i][j] + arr[j][i];
			}
		}
		diff = min(diff, abs(star - link));
		return;
	}

	for (int i = now; i < n; i++) {
		used[i] = true;
		dfs(i + 1, cnt + 1);
		used[i] = false;
	}
}

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

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

	dfs(0, 0);
	cout << diff;
	return 0;
}

🥜 채점