[java] 14889 스타트와 링크

1. 문제 링크 및 문제

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

1-1 문제 요약

: N*N의 배열에서 N/2 의 명으로 이루어진 2개의 팀으로 나뉨.
(array[i][j] + array[j][i]) - (array[x][y]+array[y][x]) 의 값이 (i,j,x,y 는 다 다른 수) 최솟값인 경우

2. 해결 방법 생각해보자 ...

팀 내부 인원을 변경하며 모든 경우 탐색 = 백트래킹 방법
1. 팀을 나눔. visited 로 구분
2. count 로 인원확인, count == N/2 일 때 능력치 계산

3. 코드

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

public class Main {

    static int N;
    static int[][] arr;
    static boolean[] visited;
    static int MinResult = Integer.MAX_VALUE;

    public static void main(String[] args) throws IOException{
        // 값 입력받기 -->
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        arr = 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++){
                arr[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        //<-- 

        MakeTeam(0,0);
        System.out.println(MinResult);
    }

    public static void MakeTeam(int count, int idx){
        if(count == N/2){
            int ans = 0;
            int Ateam = 0;
            int Bteam = 0;
            for(int i=0;i<N;i++){
                for(int j=i+1;j<N;j++){
                    if(visited[i] && visited[j]){
                        Ateam += arr[i][j] + arr[j][i];
                    }else if (!visited[i] && !visited[j]){
                        Bteam += arr[i][j] + arr[j][i];
                    }
                }
            }
            ans = Math.abs(Ateam-Bteam);
            MinResult = Math.min(ans, MinResult);
            return;
        }

        for(int i=idx;i<N;i++){
            if(visited[i]) continue;
            visited[i] = true;
            MakeTeam(count+1,i+1);
            visited[i] = false;
        }
    }
}

! 놓친 점

시간초과

참고

https://infodon.tistory.com/63