[백준] 14889번 스타트와 링크

1) 생각

항상 짝수로 주어지는 N명의 사람이 2개의 팀으로 나뉘어 경기를 할 때 팀이 되는 사람들은 서로에게 시너지 효과를 불어넣어 능력치를 향상시킨다. 이때 양팀의 능력치가 최소값이 되도록 팀을 꾸려라.

처음 생각

처음에는 탐색에서 left 팀과 right 팀을 각각 더해가면서 left의 개수와 right의 개수가 둘 다 n/2개가 되면 두 값을 - 시켜서 그 값의 최소값을 구하는 방향으로 시도하였다. => 탐색을 할 때마다 2개의 반복문을 돌면서 계속적으로 더하였기에 값을 구하기가 쉽지 않았다.

다음 생각

두 팀의 숫자가 n/2로 같으므로 한 팀이 꾸려지면 다른 팀은 자연스럽게 꾸려질 수 있다. 따라서 한 쪽 팀만 체크를 하면서 탐색을 하고 n/2 가 되면 미리 구해둔 배열의 합 값에서 해당 값을 빼주었다.

=> 미리 구해둔 배열의 합 값은 모든 경우의 수를 더한 것이라 잘 못된 값이였다.

다음 생각

한 팀을 미리 더한값으로는 다른 팀의 더한 값을 구할 수 없기에 탐색 과정에서는 누구를 선발 한 것인지만 방문 표시로 체크하고 개수가 n/2가 되었을 때, 방문 표시가 되어있는 사람과 되어있지 않은 사람들로 팀을 꾸리고 그 꾸린 팀을 가지고 시너지 효과의 합계를 구해 답을 구하였다.

=> 시간초과

2) 방안

모든 Case를 따지려고하니 '시간 초과'가 나왔기 때문에 각각의 선수들의 능력치 합을 구하는 과정을 1개로 통합하였고, 한 팀을 꾸릴때 즉, 탐색할 때 이전 선수를 뽑았으면 다시 그 선수를 뽑지 않아도 되기때문에 현재까지 돈 반복문의 Index를 다음 재귀의 변수로 넘겨주어 그 이후부터 탐색할 수 있도록 하였다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main{
    static int[][] arr;
    static int n,sum;
    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];
        
        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());
            }
        }
        visited = new boolean[n];
        min = Integer.MAX_VALUE;
        solve("",0,0);
        System.out.println(min);
    }
    
    static boolean[] visited;
    static int min;
    private static void solve(String left,int lCnt,int idx) {
        if(lCnt==n/2) {
            int leftSum = 0;
            int rightSum = 0;
            
            int[] arr2 = new int[n/2];
            int[] arr3 = new int[n/2];
            int idxL = 0;
            int idxR = 0;
            for(int i=0;i<n;i++) {
                if(visited[i])
                    arr2[idxL++] = i;
                else
                    arr3[idxR++] = i;
            }
            for(int i=0;i<n/2;i++) {
                for(int j=i+1;j<n/2;j++) {
                    leftSum += arr[arr2[i]][arr2[j]];
                    leftSum += arr[arr2[j]][arr2[i]];
                    rightSum += arr[arr3[i]][arr3[j]];
                    rightSum += arr[arr3[j]][arr3[i]];
                }
            }
            min = Math.min(min, Math.abs(rightSum-leftSum));
            return;
        }
        if(lCnt>n/2) return;
        for(int i=idx;i<n;i++) {
            if(visited[i]) continue;
            visited[i] = true;
            solve(left+" "+i,lCnt+1,i);
            visited[i] = false;
        }
    }
}