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

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

14889번: 스타트와 링크

 

지문을 잘 읽은 후에 풀어야 한다고 느낀 문제!

 

예제 2번에서 6개의 팀원이 있을 때, 0,1,3번이 팀을 이룬다면

스타트팀은 해당 부분의 합으로 능력치로 결정된다.

 

자동으로 링크팀은 2,4,5번으로 해당 부분의 합이다.

 

Sii는 항상 0이기 때문에 i==j일때는 값을 더하지 않았고 

스타트팀에 들어간 팀원은 ArrayList에 담아놓고 링크팀 계산에 엮기지 않도록 하였다.

 

 

package BOJ_SS;

import java.util.*;

public class boj14889 {
	public static int[][] con;
	public static int[] num;
	public static int min = Integer.MAX_VALUE, n , sums;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
	    n = sc.nextInt();
	    num = new int[n/2];
	    con = new int[n][n];
	    
	    for(int i=0; i<n; i++) {
	    	for(int j=0; j<n; j++){
	    		int k = sc.nextInt();
	    		con[i][j] = k;
	    		sums += k;
	    	}
	    }
	    
	    dfs(0, num, 0);
	    
	    System.out.println(min);
	}
	
	public static void dfs(int cnt, int[] nums, int idx) {
		if(cnt == n/2) {
			int res = subs();
			if(Math.abs(res) < min)
				min = res;
			return ;
		}
		
		for(int i=idx; i<n; i++) {
			nums[cnt]=i;
			dfs(cnt+1, nums, i+1);
		}
	}
	
	public static int subs() {
		int sum1=0, sum2=0;
		ArrayList<Integer> concludes = new ArrayList<>();
		
		for(int i=0; i<n/2; i++) {
			for(int j=i+1; j<n/2; j++) {
				int n1 = num[i];
				int n2 = num[j];
				
				sum1 += con[n1][n2];
				sum1 += con[n2][n1];
				if(!concludes.contains(n1))
					concludes.add(n1);
				if(!concludes.contains(n2))
					concludes.add(n2);
			}
		}
		for(int i=0; i<n; i++) {
			for(int j=0; j<n; j++) {
				if(i==j)
					continue;
				if(concludes.contains(i) || concludes.contains(j))
					continue;
				
				sum2 += con[i][j];
				sum2 += con[j][i];
			}
		}
		sum2/=2;
		
		
		return Math.abs(sum2-sum1);
	}
}