백준 14889번 : 스타트와 링크 풀이 (Java)

www.acmicpc.net/problem/14889

14889번: 스타트와 링크

Solution

조합 + 브루트포스 문제이다.

1번부터 N번까지 중에, start 팀에 들어갈 N / 2 명을 뽑으면 나머지는 자연스레 link 팀이 된다.

나는 isStart 라는 boolean 배열에 뽑은 결과를 기반으로 true 면 start 팀, false 면 link 팀으로 생각하고,

이중 for문을 돌면서 값을 각각 더해줬다. 별로 어렵지 않으니 코드를 보자.

 

Source Code

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    private static BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
    private static BufferedWriter bufferedWriter = new BufferedWriter(new OutputStreamWriter(System.out));
    private static int N, startSum, linkSum, answer;
    private static int[] people;
    private static boolean[] isStart;
    private static int[][] S;
    private static void input() throws IOException {
        N = Integer.parseInt(bufferedReader.readLine());
        people = new int[N];
        S = new int[N][N];
        startSum = 0;
        linkSum = 0;
        answer = Integer.MAX_VALUE;
        isStart = new boolean[N];
        for(int i = 0 ; i < N; i++) {
            StringTokenizer st = new StringTokenizer(bufferedReader.readLine());
            people[i] = i+1;
            for(int j = 0; j < N; j++) {
                S[i][j] = Integer.parseInt(st.nextToken());
            }
        }
    }

    private static void startCombi(int cnt, int start, int[] arr) {
        if(cnt == N / 2) {
            for(int i = 0 ; i < N/2; i++) {
                isStart[arr[i] - 1] = true;
            }
            for(int i = 0; i < N-1; i++) {
                for(int j = i+1; j < N; j++) {
                    if(isStart[i] && isStart[j]) {
                        startSum += S[i][j] + S[j][i];
                    } else if(!isStart[i] && !isStart[j]) {
                        linkSum += S[i][j] + S[j][i];
                    }
                }
            }
            answer = Math.min(answer, Math.abs(linkSum - startSum));
            startSum = 0;
            linkSum = 0;
            isStart = new boolean[N];
            // 초기화 해주는 것 잊지말자. 전역변수이기 때문이다.
            return;
        }
        for(int i = start; i < N; i++) {
            arr[cnt] = people[i];
            startCombi(cnt+1, i + 1, arr);
        }
    }

    private static void solve() throws IOException {
        startCombi(0, 0, new int[N/2]);
        System.out.println(answer);
    }

    public static void main(String[] args) throws IOException {
        input();
        solve();
        bufferedReader.close();
        bufferedWriter.close();
    }
}