백준 14889 스타트와 링크(JAVA)

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

14889번: 스타트와 링크

 

 

 

풀이)

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.StringTokenizer;

public class Main_BJ_14889_스타트와링크 {
    static int[][] map;
    static int n, ans = Integer.MAX_VALUE;
    static boolean[] visited;
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(br.readLine());
        map = new int[n][n];
        visited = new boolean[n];
        for(int i=0; i<n; i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            for(int j=0; j<n; j++){
                map[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        comb(0, 0);
        System.out.println(ans);

    }//main
    private static void comb(int idx, int cnt){
        if(cnt == n/2){
            cal();
            return;
        }

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

            visited[i] = true;
            comb(i+1, cnt+1);
            visited[i] = false;
        }

    }//comb
    private static void cal(){
        int start=0;
        int link=0;
        for(int i=0; i<n; i++){
            for(int j=0; j<n; j++){
                if(visited[i] && visited[j])
                    start += map[i][j]+map[j][i];
                else if(!visited[i] && !visited[j])
                    link += map[i][j]+map[j][i];
            }
        }
        start /= 2;
        link /= 2;
        ans = Math.min(ans, Math.abs(start-link));
    }
}

조합으로 경우의 수를 구하고, start와 link에 해당하는 점수를 구해주면 된다.

이때, for문으로 돌릴 경우 이중으로 더해진다는 점을 참고하기!!!

(아니면 for문 내에서 자체적으로 두 번 안 더하게끔 하면 된다. 그걸 이제 보고 생각남..ㅎ)

 

처음에는 무조건 4팀중 반반으로 나눠야 하는줄 알고,,,,,,, 실버2맞나...? 생각보다 더 높아야 하는거 아닌가...? 했는데

그게 아니었고 그냥 내가 잘못 본거였다...ㅠ

문제 똑바로 잘 읽기...ㅎ