문제 링크 : https://www.acmicpc.net/problem/14889
Solution
주어진 N 명의 사람들을 두 팀으로 나눈 뒤에 능력치의 차이가 최소가 되는 값을 구하는 문제입니다.
N 명 중에서 N/2 명 뽑아야 하기 때문에 조합(Combination) 을 사용하였습니다.
조합에 대한 포스팅 https://bcp0109.tistory.com/15
스타트팀은 visited 값을 true, 링크 팀은 visited 값을 false 로 하여 각 팀의 능력치 합을 따로 구해서 최소값을 찾아주시면 됩니다.
** 주의사항 1.
능력치의 차를 구해야 하기 때문에 절대값으로 계산해야합니다. Math.abs 함수를 사용해줍시다.
** 주의사항 2.
2 명이 팀일때는 예시에 나온대로
(2, 1) + (1, 2)
(3, 4) + (4, 3)
이렇게 각 팀의 능력치를 구할수 있습니다.
3 명이 팀일때는
(1, 2) + (2, 1) + (1, 3) + (3, 1) + (2, 3) + (3, 2)
(4, 5) + (5, 4) + (4, 6) + (6, 4) + (5, 6) + (6, 5)
이렇게 각 팀의 능력치의 합을 구해야 합니다.
Java Code
import java.util.*;
import java.io.*;
// https://www.acmicpc.net/problem/14889
class Main {
static int stoi(String s) { return Integer.parseInt(s); }
static int n;
static boolean[] visited;
static int[][] arr;
static int min = 987654321;
public static void main(String[] args) throws Exception {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st;
n = stoi(br.readLine());
visited = new boolean[n+1];
arr = new int[n+1][n+1];
for(int i=1; i<n+1; i++) {
st = new StringTokenizer(br.readLine());
for(int j=1; j<n+1; j++) {
arr[i][j] = stoi(st.nextToken());
}
}
comb(1, 0);
System.out.println(min);
}
// 모든 팀의 조합 구하기
static void comb(int start, int depth) {
if(depth == n/2) {
min = Math.min(min, getAbilityDifference());
return;
}
for(int i=start; i<n+1; i++) {
if(visited[i] != true) {
visited[i] = true;
comb(i+1, depth+1);
visited[i] = false;
}
}
}
// 팀의 능력치 차이를 구하기
static int getAbilityDifference() {
int sumStart = 0;
int sumLink = 0;
for(int i=1; i<n+1; i++) {
for(int j=1; j<n+1; j++) {
// true 면 스타트팀
if(visited[i] && visited[j])
sumStart += arr[i][j];
// false 면 링크팀
if(visited[i] != true && visited[j] != true)
sumLink += arr[i][j];
}
}
return Math.abs(sumStart - sumLink);
}
}
Python Code
# -*- coding: utf-8 -*-
import sys
import itertools
N = 0
arr = []
def team(member):
allMember = [i for i in range(N)]
start_team = []
link_team = []
## 멤버 선택
for i in allMember:
if i in member:
start_team.append(i)
else:
link_team.append(i)
start_sum = 0
for i in start_team:
for j in start_team:
start_sum += arr[i][j]
link_sum = 0
for i in link_team:
for j in link_team:
link_sum += arr[i][j]
return abs(start_sum - link_sum)
def solve(members):
## 모든 경우의 수 뽑기
combination_members = itertools.combinations(members, int(N/2))
selected_members = list(combination_members)
length = int(len(selected_members)/2)
minVal = sys.maxsize
for member in selected_members[:length]:
minus = team(member)
if minVal > minus:
minVal = minus
print(minVal)
if __name__ == '__main__':
N = int(sys.stdin.readline())
members = [i for i in range(N)]
for i in range(N):
arr.append(list(map(int, sys.stdin.readline().split())))
solve(members)