백준_14899_스타트와링크

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

스타트와 링크 문제를 정리 해보자면

1. N 명의 팀원을 두팀으로 나눈다(문제에선 N 이  짝수로만 주어진다.)

 

2. 두팀(A 팀 ,B 팀) 으로 나누어 졌을때 각팀원들의 능력치의 합을 구해 A팀의 능력치의 합 과 B팀의 능력치의 합의 차이를 최소화 하는것이다.

 

3. 위 2번에서 헷갈리지 말아야하는 부분은 예를들어 1번과 2번이팀이고 3번과 4번이 팀이라고 가정하자

 

1, 2 번이 속한 팀의 능력치의 합 :

1번이 2번을 만나 능력치 10 을 얻었다고 가정하자 (위배열로 예를 들면 arr[1][2] )

2 번은 1번을 만나 능력치 8 을 얻었다고 가정하자 (마찬가지로 arr[2][1]) 

즉 1, 2 번이 속한 팀원들의 능력치의 합은  10 (arr[1][2]) + 8 (arr[2][1]) = 18 이다.

 

4. 위에 사항만 고려해준다면 백트래킹을 사용해서 팀을 나눌때 마다 각 팀의 총 능력치의 차이의 최소값을 구해주면된다.

import java.util.Scanner;

public class Bj_14899 {
	static int n;
	static int[][] map;
    // 불린형 체크배열을 팀을 나누기위해 사용한다.
	static boolean check[];
	static int ans = Integer.MAX_VALUE;
	public static void main(String[] args) {
		// TODO Auto-generated method stub
		Scanner sc = new Scanner(System.in);
		n = sc.nextInt();
		map = new int[n + 1][n + 1];
		check = new boolean[n + 1];
		
		for(int i = 1; i <= n; i++) {
			for(int j = 1; j <= n; j++) {
				map[i][j] = sc.nextInt();
			}
		}
		
		divideTeam(0, 1);
		System.out.println(ans);
		
	}
    
	static void divideTeam(int count, int index) {
    // 만약 팀원을 n / 2 명을 선택했다면 능력치 차이값을 구해준다
		if(count == n / 2) {
			ans = Math.min(ans, getDiff());
			return;
		}
        // index 를 사용해서 이미 팀을 나눈경우는 생략해준다.
		for(int i = index; i <= n; i++) {
			if(!check[i]) {
				check[i] = true;
				divideTeam(count + 1, i);
				check[i] = false;
			}
		}
	}
    // 각팀의 능력치의 합을 구해준다.
	static int getDiff() {
		int team_a = 0;
		int team_b = 0;
		for(int i = 1; i <= n; i++) {
			for(int j = 1; j <= n; j++) {
            // 자기 자신과는 팀을 이룰 필요가없다.
				if(i != j) {
                // 체크가 둘다 됬다는것은 같은 팀
					if(check[i] && check[j]) {
						team_a += map[i][j];
                        // 체크가 둘다 되지 않았다는것도 역시 같은팀
					}else if(!check[i] && !check[j]) {
						team_b += map[i][j];
					}
				}
			}
		}
		return Math.abs(team_a - team_b);
	}
}