문제 링크 : 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(10);
        System.out.println(min);
    }
 
    // 모든 팀의 조합 구하기
    static void comb(int startint 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
 
= 0
arr = []
 
def team(member):
    allMember = [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 = [for i in range(N)]
 
    for i in range(N):
        arr.append(list(map(int, sys.stdin.readline().split())))
 
    solve(members)
    


+ Recent posts