[boj] 백준 15661 스타트 링크 (Java) - 완전탐색

[문제]

https://www.acmicpc.net/problem/15661

15661번: 링크와 스타트

 

[풀이]

이런 조합+완전탐색 유형의 문제가 최근 코테에 꼭 한 문제씩은 출제되는 것 같다..

 

팀은 1명 이상으로 구성되면 된다. 따라서 1명~n/2명까지의 팀원에 대해서 선택될 수 있는 모든 조합을 찾는다. 예를 들어 6명이면 3명을 뽑는 조합까지만 구하면 된다. 그 이후 4명을 뽑는 조합은 어차피 2명을 뽑는 조합에서 구해졌을 것이기 때문에..스타트팀과 링크팀의 최솟값 차이만 구하면 되므로 2명 4명이 어느 팀으로 배정되는지는 상관없다.

조합을 찾았으면 이제 선택된 스타트팀의 능력치합과 그 외의 링크팀의 능력치 합을 구해서 차이의 최솟값을 찾으면 된다.

 

[코드]

 

package 브루트포스;

import java.io.*;
import java.util.*;
import java.util.stream.Collectors;

public class boj_15661_스타트링크 {
    static int n;
    static int answer = Integer.MAX_VALUE;
    static int[][] score;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        //스타트 팀의 능력치와 링크 팀의 능력치의 차이를 최소로 하려고 한다
        n = Integer.parseInt(br.readLine());

        StringTokenizer st;
        score = new int[n][n];
        for(int i=0; i<n; i++){
            st = new StringTokenizer(br.readLine());
            for(int j=0; j<n; j++){
                score[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        boolean[] visited;
        for(int i=1; i<=n/2; i++){
            //i명, n-i명으로 팀을 나눈다.

            //i명 선택하기. 조합
            visited = new boolean[n];
            dfs(0, i, 0, visited);
        }

        System.out.println(answer);

    }

    public static void dfs(int depth, int cnt, int idx, boolean[] visited){
        if(depth==cnt){
            //i명이 선택되었으면, 두 팀의 능력치 차이 비교
            answer = Math.min(answer, calculate(visited));
            return;
        }

        for(int i=idx; i<n; i++){
            if(visited[i]) continue;

            visited[i] = true;
            dfs(depth+1, cnt, i+1, visited);

            visited[i] = false;
        }
    }

    public static int calculate(boolean[] visited){
        //능력치 차이 비교
        int t1sum = 0;
        int t2sum = 0;
 
        for(int i=0; i<n-1; i++){
            for(int j=i; j<n; j++){
                //둘다 team1 선수라면
                if(visited[i] && visited[j]){
                    t1sum += score[i][j];
                    t1sum += score[j][i];
                }
                else if(!visited[i] && !visited[j]) {
                    t2sum += score[i][j];
                    t2sum += score[j][i];
                }
            }
        }

        return Math.abs(t1sum-t2sum);
    }
    
}