[BOJ] 스타트와 링크

[14889] 스타트와 링크

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

• N명을 N/2명씩 두 팀으로 나누려고 한다. (4 <= N <= 20, N은 짝수)
• 두 팀의 능력치를 구한 다음, 차이의 최소값을 구하는 문제
• S[i][j] = i 번 사람과 j 번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치
• 팀의 능력치 : 팀에 속한 모든 쌍의 S[i][j] 집합

 

 

Solution

• 순열을 사용한 완전탐색
• a[] 배열에 0을 N/2개, 1을 N/2개 넣어서 모든 순열을 구하는 것으로 다 해볼 수 있다.
• 0이면 스타트 팀, 1이면 링크 팀
• 0 아니면 1의 조합이기 때문에 모든 순열을 구하면 같은 순열을 두 번 계산하는 것과 같아서 a[0]이 1이 되면 do-while문을 종료한다.

 

 

소스코드

import java.util.Scanner;

public class Main {
	public void go() {
		Scanner sc = new Scanner(System.in);
		int n = sc.nextInt();
		int[][] s = new int[n][n];
		int[] a = new int[n];
		int[] start = new int[n / 2];
		int[] link = new int[n / 2];

		for (int i = 0; i < n; i++) {
			for (int j = 0; j < n; j++) {
				s[i][j] = sc.nextInt();
			}
		}
		for (int i = n / 2; i < a.length; i++) {
			a[i] = 1;
		}
		int answer = Integer.MAX_VALUE;
		int ps, pl;
		do {
			if(a[0] == 1) break;
			int idx = 0;
			for (int i = 0; i < n; i++) {
				if (a[i] == 0) {
					start[idx++] = i;
				}
			}
			idx = 0;
			for (int i = 0; i < n; i++) {
				if (a[i] == 1) {
					link[idx++] = i;
				}
			}
			ps = 0;
			pl = 0;
			ps = calc(s, start); 
			pl = calc(s, link);
			answer = Math.min(answer, Math.abs(ps - pl));
		} while (next_permutation(a, n));
		System.out.println(answer);
	}

	public int calc(int[][] s, int[] team) { // 각 팀의 능력치 합 계산
		int sum = 0;
		for (int i = 0; i < team.length - 1; i++) { 
			for (int j = i + 1; j < team.length; j++) {
				sum += s[team[i]][team[j]];				
				sum += s[team[j]][team[i]];
			}
		}
		return sum;
	}
	
	public boolean next_permutation(int[] a, int n) { // 다음 순열
		int i = n - 1;
		while (i > 0 && a[i - 1] >= a[i])
			i -= 1;
		if (i <= 0)
			return false;
		int j = n - 1;
		while (a[i - 1] >= a[j])
			j -= 1;
		swap(a, i - 1, j);
		j = n - 1;
		while (i < j) {
			swap(a, i, j);
			i += 1;
			j -= 1;
		}
		return true;
	}

	public void swap(int[] a, int i, int j) {
		int temp = a[i];
		a[i] = a[j];
		a[j] = temp;
	}

	public void print(int[] arr) {
		for (int i = 0; i < arr.length; i++) {
			System.out.print(arr[i] + " ");
		}
		System.out.println();
	}

	public static void main(String[] args) {
		Main main = new Main();
		main.go();
	}
}