[백준] 15661번 링크와 스타트 풀어보기 [Java]

이 문제가 틀려있길래 풀었는데, 왜 틀렸었지라는 의문이 들었다....

사람들을 두 팀으로 나눠서 능력치를 비교하여서, 최솟값을 찾는 문제이다.

각 사람들은 자기와 같은 팀을 이룬 사람과 함께 할 때 능력치가 달라진다. 팀의 능력치는 모든 쌍의 능력치 합을 구하는 것이다. (i,j)인 경우와 (j,i)인 경우 능력치가 다르기 때문에 모두 더해준다.

 

👨‍🏫  풀이

N : 총 인원 수

링크 팀이 1~ N/2 인원을 가질 수 있다. 그래서 1~N/2 각각에서 팀을 이룰 수 있는 경우의 수를 구해줘서 최솟값을 구하면 된다.

조합 문제처럼 풀면 된다.

 

👨🏻‍💻 코드

package 번15661;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Stack;

public class Main {
    static int N;
    static int[][] values;
    static boolean[] isPicked;
    static int ans = Integer.MAX_VALUE;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        values = new int[N][N];
        isPicked = new boolean[N];
        for(int i = 0 ; i < N ; i++){
            values[i] = Arrays.stream(br.readLine().split(" ")).mapToInt(n -> Integer.parseInt(n)).toArray();
        }

        for(int i = 1 ; i <= N / 2 ; i++){
            Arrays.fill(isPicked, false);
            dfs(i,0,0);
        }

        System.out.println(ans);
    }

    static void dfs(int maxPick,int idx, int picked){
        if(maxPick == picked){
            calValuesDiff();
        } else {
            for(int i = idx ; i < N ; i++){
                if(isPicked[i]) continue;
                isPicked[i] = true;
                dfs(maxPick, i+1, picked + 1);
                isPicked[i] = false;
            }
        }
    }

    private static void calValuesDiff() {
        ArrayList<Integer> picked = new ArrayList<>();
        ArrayList<Integer> unpicked = new ArrayList<>();
        for(int i = 0 ; i < N ; i++){
            if(isPicked[i]) picked.add(i);
            else unpicked.add(i);
        }
        int pickedValues = calValues(picked);
        int unpickedValues = calValues(unpicked);
        ans = Math.min(ans, Math.abs(pickedValues - unpickedValues));
    }

    private static int calValues(ArrayList<Integer> indexs) {
        int v = 0;
        for (Integer i : indexs) {
            for (Integer j : indexs) {
                v += values[i][j];
            }
        }
        return v;
    }
}