백준 - 14889

문제

입출력

풀이

예제 1번을 기준으로
[(1,2),(3,4)],[(1,3),(2,4)],[(1,4),(2,3)]
경우의 수가 주어지고, 가장 차이가 적은 경우의 수는 6,6인 경우 0이다.
팀원 수 N은 항상 짝수로 주어지고(문제에서 제시하는 조건),
2차원 배열 map과 visit배열을 선언한다.

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.io.IOException;
import java.util.StringTokenizer;
 
public class Main {
	
	static int N;
	static int[][] map;
	static boolean[] visit;
	
	static int Min = Integer.MAX_VALUE; //차이 최소값을 찾아야하기 때문에 최대값으로 선언
	
	public static void main(String[] args) throws IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
 
		N = Integer.parseInt(br.readLine());
 
		map = new int[N][N];
		visit = new boolean[N];
 
 
		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
 
			for (int j = 0; j < N; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		} //입력
 
		combi(0, 0);
		System.out.println(Min);
 
	}
 
	static void combi(int idx, int count) //count=재귀의 depth
    {
		if(count == N / 2) { //N은 항상 짝수로,N/2로 팀이 나눠졌을때
			/*
			 방문한 팀과 방문하지 않은 팀을 각각 나누어
			 각 팀의 점수를 구한 뒤 최솟값을 찾는다.
			*/
			diff(); //경우의 수를 계산
			return;
		}
 
		for(int i = idx; i < N; i++) {
			// visit가 false로 방문하지않은 경우
			if(!visit[i]) {
				visit[i] = true;
				combi(i + 1, count + 1);	// 재귀 호출
				visit[i] = false;
			}
		}
	}
 
	// 두 팀 차이를 비교하는 함수 
	static void diff() {
		int team_start = 0; //첫번째 팀
		int team_link = 0; // 두번째 팀
 
		for (int i = 0; i < N - 1; i++) {
			for (int j = i + 1; j < N; j++) {
				// i 번째 사람과 j 번째 사람이 true라면 스타트팀으로 점수 플러스 
				if (visit[i] == true && visit[j] == true) {
					team_start += map[i][j];
					team_start += map[j][i];
				}
				// i 번째 사람과 j 번째 사람이 false라면 링크팀으로 점수 플러스 
				else if (visit[i] == false && visit[j] == false) {
					team_link += map[i][j];
					team_link += map[j][i];
				}
			}
		}
		// 두 팀의 점수 차이 (절댓값)
		int val = Math.abs(team_start - team_link);
		
	
		if (val == 0) { //두 팀의 점수차가 0이면 더이상 작은 수가 나올 수 없어서 종료
			System.out.println(val);
			System.exit(0);
		}
		
		Min = Math.min(val, Min); 최소값 비교
				
	}
 
}