[백준] 14889번:스타트와 링크 (Java 자바)

문제

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

14889번: 스타트와 링크

 

풀이 및 소스코드

 

조합을 통해 2팀으로 나눠준다.

n/2명의 사람을 한 팀으로 선택할 때, boolean 배열에 true로 표시된다.

n/2명의 사람을 다 뽑았다면 ( cnt == n/2 ), 능력치를 계산해준다.

 

능력치를 계산할 때는, (0,1) (0,2) (0,3) (0,4) (1,2) 이런식으로 차근차근 비교해가면서

둘다 true거나, 둘다 false 일 때를 찾아 각각 팀을 나눠 능력치를 계산해주면 된다.

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

public class Main {
	static int n;
	static int[][] map;
	static boolean[] select;
	static int res = Integer.MAX_VALUE;
	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;
		
		n = Integer.parseInt(br.readLine());
		map = new int[n][n];
		select = new boolean[n];
		for(int i=0;i<n;i++) {
			st = new StringTokenizer(br.readLine());
			for(int j=0;j<n;j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		choose_team(0, 0);
		System.out.println(res);
	}
	
	public static void choose_team(int cnt, int start) {
		if(cnt == n/2) {
			cal();
			return;
		}
		
		for(int i=start;i<n;i++) {
			select[i]=true;
			choose_team(cnt+1, i+1);
			select[i]=false;
		}
	}
	public static void cal() {
		int s = 0; // 선택된 한팀
		int ns = 0; // 나머지 한팀
		for(int i=0;i<n-1;i++) {
			for(int j=i+1;j<n;j++) {
				if(select[i]&&select[j]) {
					// 선택된 한팀에 속한다면 s에
					s += map[i][j];
					s += map[j][i];
				} else if(!select[i]&&!select[j]) {
					// 나머지 한팀에 둘다 속한다면 ns에
					ns += map[i][j];
					ns += map[j][i];
				}
			}
		}
		res = Math.min(Math.abs(s-ns), res);
		
		if(res == 0) {
			System.out.println(res);
			System.exit(0);
		}
	}
}