[백준] 14889_스타트와 링크

[문제]: 14889번: 스타트와 링크 (acmicpc.net)

 

N과 M 문제를 푸는 방법과 비슷하게 풀었다. 핵심은 if(k == m) 안에 있는 코드이다. start 팀의 조합을 찾았을 때, 선택되지 않은 사람들은 link팀으로 넣고, s[][] 배열을 참조하여 각 팀의 능력치 증가량을 합산하여 차를 구해 리턴한다.

그리고 그 차들 중 최솟값이 바로 답이 된다.

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

int n, m;
int s[21][21];
int start[11];
int link[11];
bool picked[21];
int ret = numeric_limits<int>::max();

int solution(int k, int p)
{
	if (k == m) {
		int ss = 0;
		int ls = 0;
        // 선택되지 않은 사람들은 link 팀이다.
		for (int i = 1, t = 0; i <= n; ++i)
			if (!picked[i])
				link[t++] = i;
		
        // 각 팀의 능력치 합산을 구한다.
		for (int i = 0; i < m; ++i) {
			for (int j = i + 1; j < m; ++j) {
				ss += s[start[i] - 1][start[j] - 1] + s[start[j] - 1][start[i] - 1];
				ls += s[link[i] - 1][link[j] - 1] + s[link[j] - 1][link[i] - 1];
			}
		}
		
        // 두 팀의 능력치 차를 리턴
		return abs(ss - ls);
	}

	for (int i = p + 1; i <= n; ++i) {
		if (!picked[i]) {
			start[k] = i;
			picked[i] = 1;
			ret = min(ret, solution(k + 1, i));
			picked[i] = 0;
		}
	}

	return ret;
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(nullptr);
	cout.tie(nullptr);
	cin >> n;
	m = n / 2;
	for (int i = 0; i < n; ++i)
		for (int j = 0; j < n; ++j)
			cin >> s[i][j];
	cout << solution(0, 0) << endl;
	return 0;
}

---

다음 코드는 다른 사람이 푼 코드이다.

x[i] += in; x[j] += in; 코드는 (i행의 모든 수 + j행의 모든 수) 와 같다. 

즉, n = 4일 때,

\[x[0] = s[0][0] + s[0][1] + s[1][0] + s[0][2] + s[2][0] + s[0][3] + s[3][0]\]

\[x[1] = s[0][1] + s[1][0] + s[1][1] + s[1][2] + s[1][3] + s[2][1] + s[3][1]\]

\[...\]

이다. 

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

int n, in, total;
int x[21];
int ret = numeric_limits<int>::max();

void solution(int idx, int cnt, int sum)
{
	// 한 팀을 정했으면
	if (cnt == n / 2) {
		if (ret > abs(sum)) ret = abs(sum);
		return;
	}
	
    
	if (idx < n - 1) {
		solution(idx + 1, cnt + 1, sum - x[idx]);
		solution(idx + 1, cnt, sum);
	}
}

int main()
{
	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 >> in;
			total += in;
			x[i] += in;
			x[j] += in;
		}
	}
	solution(0, 0, total);
	cout << ret << endl;
	return 0;
}