문제

BOJ

핵심

• 입력의 크기가 $20$이므로 구현에 초점을 맞춘다.
• 최대 20명이 모이고 반으로 나누어 팀을 정한다. 팀 간 능력치 합의 최소 차이를 구하는 문제이다.
• 먼저 N명이 모였을 때 각 팀원은 N / 2 명이 되며, 팀원을 뽑는 경우의 수는 N 명 중에 N / 2를 뽑는 조합으로 볼 수 있다. 1, 2, 3, 4, 5, 6 이 모였을 때 1 2 3이 A팀이라면 4 5 6은 B팀이다. A팀의 능력치는 n * n 테이블에서 다음의 y, x 좌표 [1 2] + [2 1], [1 3] + [3 1], [2 3] + [3, 2] 를 더해 구할 수 있다.
• A팀만 구하면 전체 인원 중에서 A 팀원을 빼면 B 팀원이 되므로 구해야 할 순열은 [1 2 3], [1 2 4], [1 2 5], [1 2 6], [2 3 4], [2 3 5], ... [4 5 6]이다. 이는 DFS를 이용해 쉽게 구할 수 있다.

void dfs(int depth, int start, vector<bool>& seq) {
	if (depth == n / 2) {
		// A, B 팀 능력치
		ans = min(ans, abs(sumA - sumB));
		return ;
	}
    for (int i = start; i <= n; ++i) {
		seq.push_back(i);
		dfs(depth + 1, i + 1, seq);
		seq.pop_back();
	}

}

• A팀의 능력치는 팀원이 [1 2 3] 이라고 할 때, 시너지 표에 해당하는 좌표 [1 2] + [1 3] + [2 3]를 더해 알 수 있다. 이를 식으로 표현하면 다음과 같다.

int sumA = 0;
for (int i = 0; i < (int)seq.size(); ++i) {
	for (int j = i + 1; j < (int)seq.size(); ++j)
		sumA += synergy[seq[i]][seq[j]] + synergy[seq[j]][seq[i]];
}

개선

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

int n;
int synergy[24][24];
int ans = 1e9;
void dfs(int depth, int start, vector<int>& seq) {
	if (depth == n / 2) {
		vector<int> seq2; // B팀
		unordered_set<int> teamA(seq.begin(), seq.end());
		for (int i = 1; i <= n; ++i) {
			if (teamA.find(i) == teamA.end())
				seq2.push_back(i);
		}
		int sumA = 0;
		for (int i = 0; i < (int)seq.size(); ++i) {
			for (int j = i + 1; j < (int)seq.size(); ++j)
				sumA += synergy[seq[i]][seq[j]] + synergy[seq[j]][seq[i]];
		}
		int sumB = 0;
		for (int i = 0; i < (int)seq2.size(); ++i) {
			for (int j = i + 1; j < (int)seq2.size(); ++j) 
				sumB += synergy[seq2[i]][seq2[j]] + synergy[seq2[j]][seq2[i]];
		}
		ans = min(ans, abs(sumA - sumB));
		return ;
	}
	for (int i = start; i <= n; ++i) {
		seq.push_back(i);
		dfs(depth + 1, i + 1, seq);
		seq.pop_back();
	}
}
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= n; ++j)
			cin >> synergy[i][j];
	}
	vector<int> seq;
	dfs(0, 1, seq);
	cout << ans;
}

• 위의 코드로 통과했지만, DFS로 순열을 구하면서 A팀을 선택할 때 true로 체크한다면, B팀은 당연하게 false로 검사되었다. 즉, B 팀원을 구하기 위해 전체 모인 사람에서 A 팀원을 제거 할 필요가 없어진다.

int sumA = 0; int sumB = 0;
for (int i = 1; i <= n; ++i) {
	for (int j = i + 1; j <= n; ++j) {
		if (isSelected[i] && isSelected[j])
			sumA += synergy[i][j] + synergy[j][i];
		else if (!isSelected[i] && !isSelected[j])
			sumB += synergy[i][j] + synergy[j][i];
	}
}

코드

시간복잡도

• $O(nC\frac{n}2 \times n^2)$

C++

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

int n;
int synergy[24][24];
int ans = 1e9;
void dfs(int depth, int start, vector<bool>& isSelected) {
	if (depth == n / 2) {
		int sumA = 0; int sumB = 0;
		for (int i = 1; i <= n; ++i) {
			for (int j = i + 1; j <= n; ++j) {
				if (isSelected[i] && isSelected[j])
					sumA += synergy[i][j] + synergy[j][i];
				else if (!isSelected[i] && !isSelected[j])
					sumB += synergy[i][j] + synergy[j][i];
			}
		}
		ans = min(ans, abs(sumA - sumB));
		return ;
	}
	for (int i = start; i <= n; ++i) {
		isSelected[i] = true;
		dfs(depth + 1, i + 1, isSelected);
		isSelected[i] = false;
	}
}
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(nullptr);
	cin >> n;
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= n; ++j)
			cin >> synergy[i][j];
	}
	vector<bool> isSelected(n, false);
	dfs(0, 1, isSelected);
	cout << ans;
}

Java

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {
    static int n;
    static int[][] synergy = new int[24][24];
    static int ans = Integer.MAX_VALUE;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        for (int i = 1; i <= n; i++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            for (int j = 1; j <= n; j++)
                synergy[i][j] = Integer.parseInt(st.nextToken());
        }
        boolean[] isSelected = new boolean[n + 1];
        dfs(0, 1, isSelected);
        System.out.println(ans);
    }

    static void dfs(int depth, int start, boolean[] isSelected) {
        if (depth == n / 2) {
            int sumA = 0, sumB = 0;
            for (int i = 1; i <= n; ++i) {
                for (int j = i + 1; j <= n; ++j) {
                    if (isSelected[i] && isSelected[j])
                        sumA += synergy[i][j] + synergy[j][i];
                    else if (!isSelected[i] && !isSelected[j])
                        sumB += synergy[i][j] + synergy[j][i];
                }
            }
            ans = Math.min(ans, Math.abs(sumA - sumB));
            return;
        }
        for (int i = start; i <= n; ++i) {
            isSelected[i] = true;
            dfs(depth + 1, i + 1, isSelected);
            isSelected[i] = false;
        }
    }
}