[백준] JAVA - 14889.스타트와 링크

생각

예제에서는 N=4이고 한 팀당 2명이기 때문에 (1,2)이 한팀이고 (3,4)이 나머지 팀일때 능력치의 차이를 (S12+S21), (S34+S43)의 차이로 구했습니다. 만약 한 팀당 인원이 3명이상일땐, 예를 들어 (1,2,3)인 경우일때 팀의 능력치의 차이를 계산할땐 (S12 + S21 + S13 + S31 + S23 + S32) 와 같이 계산해줘야 합니다.  

 

N개를 N/2로 각각 두 팀으로 나눕니다. 나눌수있는 모든 가능한 경우를 조합으로 뽑았습니다.

teamA와 teamB 정수형 배열을 만든다음 teamA에서 N/2만큼 조합으로 뽑았습니다. 그 다음으로 teamA에서 뽑히지 않은 번호들만 체크하여 teamB에 넣었습니다. (선택된 원소를 제외한 나머지 원소를 추출하는 더 좋은 방법이 있을것 같은데 일단 이렇게 구현했습니다..ㅎㅎ 스터디 때 다른 친구들은 어떻게 구현했는지 배워야겠습니다!!)

 

이제 각 팀의 능력치의 차이를 계산해야 합니다! 

이중포문을 사용하여 가능한 팀에 속한 각각의 쌍이 map[i][j]일때 map[j][i]를 더해줬습니다. 이렇게 구한 각 팀의 능력치 차이가 최소가 되는 값을 찾아 출력해주면 됩니다.

 

Java code

package com.java.algorithm;

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

public class Baekjoon_14889_스타트와링크 {
/**
 * N개중 N/2명 조합으로 뽑는다.
 * 최소값 가장 작은거 출력
 * @throws IOException 
 * @throws NumberFormatException 
 * */
	static int N;
	static int[][] map;
	static int[] teamA;
	static int[] teamB;
	static int ans = Integer.MAX_VALUE;
	public static void main(String[] args) throws NumberFormatException, IOException {
		
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		
		map = new int[N][N];
		
		teamA = new int[N/2];
		teamB = new int[N/2];
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < N; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		comb(0, 0, N/2); // 두팀으로 나누기 -> teamA, teamB 정해짐
		System.out.println(ans);
		
	}
	private static void comb(int cnt, int start, int total) {
		if(cnt == total) {
			boolean[] isSelected = new boolean[N];
			
			for (int i = 0; i < N/2; i++) {
				isSelected[teamA[i]] = true;
			}
			int j=0;
			for (int i = 0; i < N; i++) {
				if(!isSelected[i]) {
					teamB[j++] = i;
				}
			}
			int sum_a=0, sum_b=0;
			for (int i = 0; i < N/2; i++) {
				for (int k = i+1; k < N/2; k++) {
					if(i==k) continue;
					sum_a += map[teamA[i]][teamA[k]];
					sum_a += map[teamA[k]][teamA[i]];
					
					sum_b += map[teamB[i]][teamB[k]];
					sum_b += map[teamB[k]][teamB[i]];
				}
			}
			ans = Math.min(ans, Math.abs(sum_a-sum_b));
			return;
		}
		for (int i = start; i < N; ++i) {
			teamA[cnt] = i;
			comb(cnt+1, i+1, total);
		}
		
	}

}