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

📌 문제

BOJ 바로가기

n명의 사람이 주어졌을 때 n/2명씩 스타트 팀, 링크 팀에 넣는다. 두 팀의 능력치가 최소가 되도록 팀을 구성하고, 능력치의 차이를 출력한다.

🗡 풀이

브루트포스, 백트래킹 문제이다. 어렵지 않게 풀릴 거라 생각했는데 생각보다 오래 걸렸다. 이유는

• 전체 스킬에서 A팀 스킬을 빼면 B 스킬을 구할 수 있을 거라고 안일하게 생각했다.
• B 벡터를 비워주지 않아서 계속해서 잘못된 답이 나왔다.
  저번에도 큐를 비워주지 않아서 디버깅에 오랜 시간이 걸린 일이 있었는데... 주의해야겠다😥

결국 정답을 맞히긴 했지만... 코드가 길어져버렸다. 다른 분들의 답을 보니 더 짧고 간결하게 짤 수 있었다는 사실을 깨달았다ㅎㅎ;
다음에 이러한 유형의 문제를 다시 마주치게 된다면

• next_permutation 함수를 이용해서 간단히 팀을 구성하고
• B 팀을 구성하는 코드를 삭제하고 다음과 같이 간결하게 짤 것이다.

// A, B 스킬 계산
for (int i = 1; i <= n ; i++) {
	for (int j = 1; j <= n; j++) {
		if (i, j가 A팀이면)
        	A_skill += skill[i][j];
        else if (i, j가 모두 A팀이 아니면)
            B_skill += skill[i][j];
	}
}

🚩 소스코드

#include <iostream>
#include <algorithm>
#include <vector>
#include <stdlib.h>
using namespace std;

int n, skill[21][21], ans = 100000000;
vector<int> A, B;

void go(int people, int start) {
	if (people == n / 2) {
		int A_skill = 0, B_skill = 0;
		// B 팀 구성 (A에 없는 숫자라면 B에 넣는다)
		for (int i = 1; i <= n; i++) {
			int flag = true;
			for (int j = 0; j < A.size(); j++) {
				if (i == A[j]) {
					flag = false;
					break;
				}
			}
			if (flag)
				B.push_back(i);
		}
		// A 스킬 계산
		for (int i = 0; i < A.size(); i++) {
			for (int j = 0; j < A.size(); j++) {
				A_skill += skill[A[i]][A[j]];
			}
		}
		// B 스킬 계산
		for (int i = 0; i < B.size(); i++) {
			for (int j = 0; j < B.size(); j++) {
				B_skill += skill[B[i]][B[j]];
			}
		}
		// 결과 도출
		ans = min(ans, abs(A_skill - B_skill));
		B.clear(); // 비워주지 않으면 계속해서 쌓임!
		return;
	}
	for (int i = start; i <= n; i++) {
		A.push_back(i);
		go(people + 1, i + 1);
		A.pop_back();
	}
}

int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> skill[i][j];
		}
	}
	go(0, 1);
	cout << ans;
}