백준 14889번. 스타트와 링크 (Java, Python)

문제 링크 : 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)