백준 14889 스타트와 링크 Java

 

삼성 sw 기출문제인 스타트와 링크 문제이다. 정답률을 50%로 sw 기출문제 중에선 쉬운 편인것 같다

 

알고리즘 분류는 브루트 포스로 분류되어있지만

백트래킹을 활용해서 문제를 풀었다.

 

문제 내용은 짝수인 사람 수 N이 주어지고

2개의 팀이 N/2명씩 나눠진다.

N*N으로 팀원들의 능력치가 주어지면 

2개의 팀 사이에 팀원들의 능력치 차이가 최소로 됐을 때

그 능력치 차이를 출력하면 된다.

 

N의 범위가 20으로 작기 때문에

가능한 팀의 구성을 백트래킹으로 전부 구하고

구해질때마다 팀원들의 능력치를 계산해서

그 차이가 최소인 값을 찾아내는 방식으로 구현하였다.

 

백트래킹으로 team이라는 boolean형 배열에 true가 3개가 되었을 때

계산 메소드를 호출했다. 계산 메소드는 2중 for문으로

능력치가 주어진 N*N의 배열을 돌며 계산하였다.

 

team배열에 true인 인덱스는 스타트팀 false인 인덱스는 링크팀으로 나누어서 

i와 j가 전부 true일 땐 스타트팀에 그 능력치를 더하고

i와 j가 전부 false일 땐 링크팀에 그 능력치를 더하고

반복문을 빠져나왔을 때 차이를 구해서 최솟 값을 찾았다.

 

능력치의 차이를 계산하는 다른 빠른 방법이 있다면 뭐가 있을까.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Q14889 {
    public static int [][] a;
    public static int n;
    public static int ans = Integer.MAX_VALUE;
    public static boolean [] team = new boolean[21];
 
    public static void makeTeam(int k, int cnt) {
        if(n/2 == cnt) {
            calculation();
        } else {
            for(int i=k; i<=n; i++) {
                if(!team[i]) {
                    team[i] = true;
                    makeTeam(i, cnt+1);
                    team[i] = false;
                }
            }
        }
    }
    
    public static void calculation() {
        int start = 0;
        int link = 0;
 
        for(int i=1; i<=n; i++) {
            for(int j=1; j<=n; j++) {
                if(i==j) continue;
                if(team[i] && team[j]) {
                    start += a[i][j];
                } else if(!team[i] && !team[j]) {
                    link += a[i][j];
                }
            }
        }
 
        ans = Math.min(ans, Math.abs(start-link));
    }
 
    public static void main(String[] args) throws IOException  {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        n = Integer.parseInt(reader.readLine());
        a = new int[n+1][n+1];
        for(int i=1; i<=n; i++) {
            StringTokenizer st = new StringTokenizer(reader.readLine());
            for(int j=1; j<=n; j++) {
                a[i][j] = Integer.parseInt(st.nextToken());
            }
        }
        makeTeam(1, 0);
        
 
        System.out.print(ans);
    }
}