[BOJ] 백준 14889 스타트와 링크

삼성 SW 코딩 테스트 준비(A형)

삼성 SW 기출 모음

출처: https://www.acmicpc.net/problem/14889

 Input 

4

0 1 2 3

4 0 5 6

7 1 0 2

3 4 5 0

 

 Output 

0

ex) 1, 2번이 스타트 팀 / 3, 4번이 링크 팀에 속한 경우 두 팀의 능력치는 아래와 같다.

    Team 1: S12 + S21 = 1 + 4 = 5

    Team 2: S34 + S43 = 2 + 5 = 7

ex) 1, 4번이 스타트 팀 / 2, 3번이 링크 팀에 속하면, 두 팀의 능력치는 아래와 같다.

    Team 1:  S14 + S41 = 3 + 3 = 6

    Team 2:  S23 + S32 = 5 + 1 = 6

두 팀의 능력치 차이를 최솟값을 출력하는 문제입니다.

 

팀을 구분할 수 있는 경우를 완전탐색하면 됩니다.

인원팀을 절반으로 구분할 때, 순서는 중요치 않습니다.

 

N = 4 ▶ 일 때, 다음과 같이 나눌 수 있습니다.

(1, 2) vs (3, 4)    (1, 3) vs (2, 4)    (1, 4) vs (2, 3)

(2, 3) vs (1, 4)    (2, 4) vs (1, 3)    (3, 4) vs (1, 2)

이때 대칭되는 구조를 볼 수 있습니다.

N = 6 ▶ {1, 2, 3, 4, 5, 6} 일 때, 다음과 같이 나눌 수 있습니다.

대칭선 이전의 팀을 보면 결과적으로 좌측에는 『1』번 선수가 속한 경우이다.

따라서 『1』 번 사람이 속한 Team 1 팀원을 선정하면 됩니다.  

N-1CN/2-1  → 5C2  중복 없는 조합

1개의 팀을 선정하면 남은 사람을 다른 팀으로 하여 능력치를 구할 수 있습니다.

---

import java.util.ArrayList;
import java.util.List;
import java.util.Scanner;

public class Main {
    
    static int[] people;
    static int N, answer = Integer.MAX_VALUE;
    static int[][] S;
    
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        N = Integer.parseInt(sc.next());
        people = new int[N+1];
        S = new int[N+1][N+1];
        
        for(int i=1; i<=N; i++) {
            for(int j=1; j<=N; j++) {
                S[i][j] = Integer.parseInt(sc.next());
            }
        }
        
        // 1 ~ N번까지 번호 부여
        for(int i=1; i<=N; i++) {
            people[i] = i;
        }
        
        List<Integer> team1 = new ArrayList<>();
        // 1번 사람을 우선 team1에 소속시킨다.
        team1.add(people[1]);
        
        // 2번 사람부터 team1에 소속시킬지 말지
        // 중복없는 조합을 구한다.(DFS)
        combination(team1, 2);
        
        System.out.println(answer);
    }
    
    // idx번째 사람을 소속시킨든지 말든지 둘 중 하나
    private static void combination(List<Integer> team1, int idx) {
        if(team1.size() == N / 2) {
            // 팀이 절반으로 나눠졌으면...
            int team1_S = 0;
            int team2_S = 0;
            for(int i=1; i<=N; i++) {
                for(int j=1; j<=N; j++) {
                    if(team1.contains(i) && team1.contains(j)) {
                        team1_S += S[i][j];
                    }else if(!team1.contains(i) && !team1.contains(j)) {
                        team2_S += S[i][j];
                    }
                }
            }
            
            answer = Math.min(answer, Math.abs(team1_S - team2_S));

            return;
        }
        
        // 더 이상 팀원 가입시킬 멤버가 없으면 종료
        if(idx > N) return;
        
        // idx번째 사람을 team1에 소속 시킨 경우
        team1.add(people[idx]);
        combination(team1, idx+1);
        
        // idx번째 사람을 team1에 소속 소속시키지 않은 경우
        
        team1.remove(team1.size()-1);
        combination(team1, idx+1);
    }
}