[백준(Baekjoon)][자바(java)] [삼성 SW 역량 테스트 기출 문제] 14889 : 스타트와 링크

 

www.acmicpc.net/problem/14889

14889번: 스타트와 링크

 

문제 풀이

 

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

public class Main {
	
	static int n, m, s[][], a1[], a2[], ts[], tl[], cs, cl, cd, cdm;  
	// team start/link, capacity start/link/diff/diff_min
	static boolean v1[], v2[];
	
	public static void com2( int k, int l ) {  // 각 팀의 팀원들 중 2명 씩 ( 팀원들의 능력치 구하기 )
		int i;
		if( k == 2 ) {
			int is, js, il, jl;
			is = ts[a2[0]];
			js = ts[a2[1]];
			il = tl[a2[0]];
			jl = tl[a2[1]];
			cs += s[is][js] + s[js][is];
			cl += s[il][jl] + s[jl][il];
			return;
		}
		for( i = l; i < m; ++i ) {
			if( !v2[i] ) {
				v2[i] = true;
				a2[k] = i;
				com2( k+1, i+1 );
				v2[i] = false;
			}
		}
	}
	
	public static void com( int k, int l ) {  // 멤버들을 반으로 두 팀 ( 팀 나누기 )
		int i;
		if( k == m ) {
			int is = 0, il = 0;
			for( i = 0; i < n; ++i ) {
				if( v1[i] )	ts[is++] = i;
				else		tl[il++] = i;
			}
			cs = cl = 0;
			com2( 0, 0 );
			cd = Math.abs( cs - cl );
			if( cdm > cd )
				cdm = cd;
			return;
		}
		for( i = l; i < n; ++i ) {
			if( !v1[i] ) {
				v1[i] = true;
				a1[k] = i;
				com( k+1, i+1 );
				v1[i] = false;
			}
		}
	}

	public static void main(String[] args) throws Exception {
		
		BufferedReader br = new BufferedReader( new InputStreamReader( System.in ) );
		n = Integer.parseInt( br.readLine() );
		s = new int[n][n];
		int i, j;
		StringTokenizer st;
		for( i = 0; i < n; i++ ) {
			st = new StringTokenizer( br.readLine() );
			for( j = 0; j < n; j++ )
				s[i][j] = Integer.parseInt( st.nextToken() );
		}
		br.close();
		
		m = n/2;
		ts = new int[m];
		tl = new int[m];
		
		a1 = new int[n];
		v1 = new boolean[n];
		a2 = new int[m];
		v2 = new boolean[m];
		
		cdm = Integer.MAX_VALUE;
		
		com( 0, 0 );
		
		System.out.println( cdm );
        
	}
}

n명의 멤버들( 0 ~ n-1의 숫자 )의 조합( com() )들을 구한 후
boolean v1[] 배열을 통해 반씩 각 팀의 배열에 넣고
각 팀에서 두 명씩 조합( com2() )을 구해 능력치의 합을 구해
두 팀의 능력치의 차를 구하고 최소값을 구함