[백준(Baekjoon)][자바(java)] 14889 : 스타트와 링크 / 백트래킹

 

www.acmicpc.net/problem/14889

14889번: 스타트와 링크

 

풀이

N명의 사람이 있을 떄

각 팀당 N/2명이 되도록 조합을 구함

그리고 그 안에서 2명씩의 조합을 구해 서로의 능력치를 더하고 모두 합하여 팀의 능력치를 구함

결국 조합 안의 조합을 구하는 문제

 

 

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

public class Main {
	
	static int n, m, c[], c2[], t_s[], t_l[], a[][], a_s, a_l, dif, dif_min;
	static boolean v[], v2[];
	
	public static void teamAbility( int cnt, int min ) {
		int i;
		if( cnt == 2 ) {
			a_s += a[t_s[c2[0]]][t_s[c2[1]]] + a[t_s[c2[1]]][t_s[c2[0]]];
			a_l += a[t_l[c2[0]]][t_l[c2[1]]] + a[t_l[c2[1]]][t_l[c2[0]]];
			return;
		}
		for( i = min; i < m; i++ ) {
			if( !v2[i] ) {
				v2[i] = true;
				c2[cnt] = i;
				teamAbility( cnt + 1, i + 1 );
				v2[i] = false;
			}
		}
	}
	
	public static void teamCombination( int cnt, int min ) {
		int i, idx_s = 0, idx_l = 0;
		if( cnt == m ) {
			a_s = 0; a_l = 0; dif = 0;
			for( i = 0; i < n; i++ ) {
				if( v[i] )
					t_s[idx_s++] = i+1;
				else
					t_l[idx_l++] = i+1;
			}
			teamAbility( 0, 0 );
			dif = Math.abs( a_s - a_l );
			dif_min = dif_min > dif ? dif : dif_min;
			return;
		}
		for( i = min; i < n; i++ ) {
			if( !v[i] ) {
				v[i] = true;
				c[cnt] = i;
				teamCombination( cnt + 1, i + 1 );
				v[i] = false;
			}
		}
	}

	public static void main(String[] args) throws IOException {
		
		BufferedReader br = new BufferedReader( new InputStreamReader(System.in) );
		StringTokenizer st;
		int i, j;
		
		n = Integer.parseInt( br.readLine() ); 	// total members num
		m = n/2;								// each team members num
		a = new int[n+1][n+1];					// ability of each member arr
		for( i = 1; i <= n; i++ ) {
			st = new StringTokenizer( br.readLine() );
			for( j = 1; j <= n; j++ )
				a[i][j] = Integer.parseInt( st.nextToken() );
		}
		
		c = new int[n];					// comb arr
		v = new boolean[n];				// comb visited
		c2 = new int[m];				// comb2 arr
		v2 = new boolean[m];			// comb2 visited
		t_s = new int[m];				// team Start member arr
		t_l = new int[m];				// team Link member arr
		dif_min = Integer.MAX_VALUE;	// min difference value
										// a_s : ability of team Start
										// a_l : ability of team Link
		teamCombination( 0, 0 );
		
		System.out.println( dif_min );
        
	}
}