[JAVA] 백준 스타트와 링크

www.acmicpc.net/problem/14889

14889번: 스타트와 링크

Sij 와 Sji 표

<예시>

4명 기준일때,

1. Combination으로 4명중 2명을 뽑는다.

 

2. 뽑은 2명에 대하여 Sij + Sji 를 실행한다.

(안뽑은 2명에 대하여 Sij + Sji를 실행한다.)

 

3. 두 각각의 더한값의 차(절대값)를 구한다.

 

4. 그 중에서 차가 가장 작은 최소값을 출력한다.

 

 

위의 예시를 일반화하면

 

 

1. Combination으로 n명중 n/2명을 뽑는다.

 

2. 뽑은 n/2명에 대하여 Sij + Sji를 이중for문으로 더한다.

static int getSum(int i, int j){
        return list.get(i).get(j);
}

for (int i=0; i<arr.length; i++) {
                for(int j=0; j<arr.length; j++){
                //getSum은 list.get(i).get(j)
                    sum+=getSum(arr[i],arr[j]);
				}
}

Combination에서 i번째와 n-1-i번째는 서로 상호반대(상호보완적)의 조합이다.

ex) 첫번째(0)에 1,3을 뽑았다면 n번째(n-1)에 0,2를뽑았다는 의미임

static ArrayList<ArrayList<Integer>> list = new ArrayList<>();
int min=Integer.MAX_VALUE;


for(int i=0; i<ans.size()/2; i++){
	//min값을 구할때, i번째와 combination개수-1-i번째 차이를 구함
       min = Math.min(Math.abs(ans.get(i)-ans.get(ans.size()-i-1)), min);
}

 

3. 두 값의 차이를 ArrayList로부터 불러와 계산하여 각각에 대한 차이값을 min값으로 비교한다.

 

4. 비교해서 최종 min값을 출력한다.

 

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

public class Main {
    static int n;
    static ArrayList<ArrayList<Integer>> list = new ArrayList<>();
    static int[] arr;
    static ArrayList<Integer> ans = new ArrayList<>();
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        n = sc.nextInt();
        arr = new int[n/2];
        //graph
        for(int i=0; i<n; i++){
            list.add(new ArrayList<>());
        }

        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                list.get(i).add(sc.nextInt());
            }
        }
        dfs(0, 0);

        int min=Integer.MAX_VALUE;
        for(int i=0; i<ans.size()/2; i++){
            min = Math.min(Math.abs(ans.get(i)-ans.get(ans.size()-i-1)), min);
        }
        System.out.println(min);
    }
    static void dfs(int at, int depth) {
        if (depth == n/2) {
            int sum=0;

            for (int i=0; i<arr.length; i++) {
                for(int j=0; j<arr.length; j++){
                    sum+=getSum(arr[i],arr[j]);
                }
            }
            ans.add(sum);
            return;
        }

        for (int i = at; i < n; i++) {
            arr[depth] = i;
            dfs(i + 1, depth + 1);
        }
    }

    static int getSum(int i, int j){
        return list.get(i).get(j);
    }
}