[백준] 14889번 스타트와 링크

www.acmicpc.net/problem/14889

14889번: 스타트와 링크

문제 설명 :

스타트 팀과 링크팀의 능력치의 차이의 최솟값 출력

문제 풀이:

N명의 사람들을 스타트 팀과 링크 팀으로 나누면서, 각 팀 능력치 합의 차이를 최소로 구해야한다. 

두 팀으로 나누기 위해서 N/2만큼 조합으로 뽑는다.

 

• team[] : S(능력치) 입력이 들어있다. 
• mask[] : 스타트팀은 true, 링크팀은 false
• startsum, linksum : 각 팀 능력치 합
• comb() : N/2 명을 뽑기 위한 조합 함수
• sol() : 각 팀 능력치 합의 최소값을 구하기 위한 함수

import java.util.Scanner;

public class Main {
	static int N,min = Integer.MAX_VALUE;
	static int[][] team;
	static boolean[] mask;
	
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		N = sc.nextInt();
		team = new int[N+1][N+1];
		mask = new boolean[N+1];
		
		for (int i = 1; i < N+1; i++) {
			for (int j = 1; j < N+1; j++) {
				team[i][j] = sc.nextInt();
			}
		}
		
		comb(1,0);
		System.out.println(min);
	}

	public static void comb(int start, int depth) {
		if(depth == N/2) {
			min = Math.min(min, sol());
			return;
		}
		for (int i = start; i < N+1; i++) {
			if(mask[i]) continue;
			mask[i] = true;
			comb(i+1, depth+1);
			mask[i] = false;
		}
		
	}

	public static int sol() {
		int startsum =0, linksum = 0;
		
		for (int i = 1; i < N+1; i++) {
			for (int j = 1; j < N+1; j++) {
				//mask 가 true 면 스타트팀, false 면 링크 팀
				if(mask[i] && mask[j]) startsum += team[i][j];
				if(!mask[i] && !mask[j]) linksum += team[i][j];
			}
		}
		
		return Math.abs(startsum - linksum);
	}
	
}