링크와 스타트

📍 문제 설명

 

💡 접근

스타트와 링크 문제와 거의 유사한 문제

스타트와 링크는 N/2명의 인원수로 구성된 2팀을 뽑아 내는 것이고 링크와 스타트는 인원수 관계 없이 1명 이상의 팀으로 2팀을 뽑아내는 것이다.

1명을 팀으로 했을 때, 2명을 팀으로 했을 때, 3명을 팀으로 했을 때를 감안해야 하므로 최종지점의 값을 1부터 n-1 까지 돌린다. 

결국 N명 중에 1,2,3명 뽑는 조합의 문제이다.

 

👩‍💻 코드

import java.util.*;

public class Main {
    static int n, m, sum, answer = Integer.MAX_VALUE;
    static int[][] board,clone;
    static boolean[] arr;
    static boolean[] visited;
    static int[] dx = {-1,1,0,0};
    static int[] dy = {0,0,-1,1};
    static StringBuilder sb = new StringBuilder();
    static int maxValue;
    public static void main(String[] args) {
        Scanner kb = new Scanner(System.in);
        Main T = new Main();
        n = kb.nextInt();
        board = new int[n][n];
        visited = new boolean[n];
        for(int i = 0; i < n; i++) {
            for(int j = 0; j < n; j++) {
                board[i][j] = kb.nextInt();
            }
        }
        //n명 중에 2팀을 뽑는다. 팀의 인원수를 m이라고 한다.
        //1명과 3명, 2명과 2명, 3명과 1명을 뽑아야한다.
        for(m = 1; m < n; m++) {
            T.solution(0, 0);
        }
        System.out.println(answer);
    }

    private void solution(int L, int s) {
        if(L == m) {
            int linkTeam = 0, startTeam = 0;
            for(int i = 0; i < n; i++) {
                for(int j = 0; j < n; j++) {
                    if(i==j) continue;
                    if(visited[i] && visited[j]) linkTeam += board[i][j];
                    if(!visited[i] && !visited[j]) startTeam += board[i][j];
                }
            }
            answer = Math.min(answer, Math.abs(linkTeam-startTeam));
        }
        else {
            for(int i = s; i < n; i++) {
                if(!visited[i]) {
                    visited[i] = true;
                    solution(L+1, i+1);
                    visited[i] = false;
                }
            }
        }
    }
}