[PS][기출문제][삼성]/[BOJ][14889][스타트와 링크]

boj14889.cpp

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

int n = 0;
int map[20][20];
int pointSum = 0;
int arr[20];
int ans = 0xFFFFFF;
bool visited[20];


int main(void) {
	cin.tie(NULL);
	ios::sync_with_stdio("false");
	cin >> n;
	int i = 0, j = 0;
	for (i = 0; i < n; i++) {
		if (i >= n / 2) arr[i] = 1;
		for (int j = 0; j < n; j++) {
			cin >> map[i][j];
			pointSum += map[i][j];
		}
	}
	do{
		int a = 0, b = 0;
		for (i = 0; i < n; i++) {
			for (j = i + 1; j < n; j++) {
				if (arr[i] != arr[j]) continue;
				if (arr[i] == 0) {
					a += map[i][j];
					a += map[j][i];
				}
				else {
					b += map[i][j];
					b += map[j][i];
				}
			}
		}
		ans = min(ans, abs(a - b));
	} while (next_permutation(arr, arr + n));
	cout << ans << "\n";
	return 0;
}

///recur 풀이

#include <cstdio>
#include <iostream>

using namespace std;

int n, arr[20][20], start[10], link[10], start_idx, link_idx, ans = 0xFFFFFF;

void recur(int depth) {
    if (!ans)
        return;
    if (depth == n) {
        int start_sum = 0, link_sum = 0;
        for (int i = 0; i < n / 2 - 1; ++i) {
            for (int j = i + 1; j < n / 2; ++j) {
                start_sum += arr[start[i]][start[j]] + arr[start[j]][start[i]];
                link_sum += arr[link[i]][link[j]] + arr[link[j]][link[i]];
            }
        }
        start_sum -= link_sum;
        if (start_sum < 0)
            start_sum *= -1;
        ans = ans < start_sum ? ans : start_sum;
        return;
    }
    if (start_idx < n / 2) {
        start[start_idx++] = depth;
        recur(depth + 1);
        --start_idx;
    }
    if (link_idx < n / 2) {
        link[link_idx++] = depth;
        recur(depth + 1);
        --link_idx;
    }
}

int main() {
    cin >> n;
    for (int i = 0; i < n; ++i)
        for (int j = 0; j < n; ++j)
            cin >> arr[i][j];
    recur(0);
    cout << ans << "\n";
    return 0;
}