[BOJ 14889] 스타트와 링크

문제

• BOJ 14889
• 문제의 저작권은 Baekjoon Online Judge에 있습니다.

접근방식

1. 전체 인원 N명을 N/2명씩 나눠줘야 한다. 이때 N=6이고 1,2,3번을 뽑으면 4,5,6은 자동으로 결정되기 때문에 뒤의 경우의 수는 따로 구해줄 필요가 없다. 그림을 그려 생각해보면 아래 규칙을 찾을 수 있다.
   
   따라서 조합 함수에서 중간에 종료되는 조건을 걸어준다. 조합을 구하는 함수 comb()에서는 뽑은 숫자를 visited배열에 true 표시해준다. 기저 조건에서는 경우의 수를 모두 구했으므로(예를 들어 1,2,3을 뽑으면) visited배열이 true인 경우와 false인 경우 각각을 N/2크기의 배열 trueArr, falseArr에 저장한다.
   이제 이 두개의 배열은 스타트팀, 링크팀이 된다. 최종 구하고자 하는 것은 두 팀의 차를 구하면 되기 때문에 어느 쪽이 어떤 팀이 되는지는 중요하지 않다.
   여기서 각 팀에서 2명을 뽑아 능력치를 계산하기 위해 순열 함수 perm()을 실행한다.
   순열인 이유는 Aij와 Aji가 다른 경우의 수이기 때문이다. 이렇게 trueArr과 falseArr의 능력치를 각각 계산해 그 차의 절대값과 Ans를 비교해서 더 작은 최소값을 Ans에 저장한다.
   순열, 조합을 작성하는 코드를 이해,암기하고 있으면 쉽게 접근할 수 있는 문제이다.
   조합은 원래 자주 사용한 방식이 아닌 뽑고 안뽑고방식을 사용했는데 이 코드도 암기해 두어야겠다.

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

//스타트와 링크
public class Boj14889 {
	static int N;
	static int[][] S;
	static int Ans; // 스타트-링크 차이 최소
	static boolean[] selected;
	static boolean[] visited;
	static int[] result;
	static int[] two;
	static int sum;

	public static void main(String[] args) throws NumberFormatException, IOException {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		S = new int[N + 1][N + 1]; // 1번~N번

		StringTokenizer st;
		for (int i = 1; i <= N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j = 1; j <= N; j++) {
				S[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		
		Ans = Integer.MAX_VALUE;
		selected = new boolean[N];
		two = new int[2];
		comb(0, 0);
		System.out.println(Ans);
	}

	//조합
	static void comb(int target, int cnt) { // 뽑은 개수, 시작숫자
		if (cnt == N / 2) {
			int[] trueArr = new int[N/2];
			int[] falseArr = new int[N/2];
			
			int j=0;
			int k=0;
			for(int i=0; i<N; i++) {
				if(selected[i]) trueArr[j++] = i+1;
				if(!selected[i]) falseArr[k++] = i+1;
			}
			visited = new boolean[N/2];
			sum = 0;
			perm(0, trueArr);
			int trueSum = sum;
			
			visited = new boolean[N/2];
			sum = 0;
			perm(0, falseArr);
			int falseSum= sum;
			
			Ans = Math.min(Math.abs(trueSum-falseSum), Ans);
			return;
		}

		if (target == N) {
			return;
		}
		
		if(cnt==0 && target>=N/2-1) return; //뒤에 경우의수는 안구해줌
		selected[target] = true;
		comb(target + 1, cnt + 1);
		sum = 0;
		selected[target] = false;
		comb(target + 1, cnt);
		sum = 0;
	}

	// 순열: 능력치의 합을 구함
	private static void perm(int cnt, int[] numbers) {
		if(cnt == 2) {//2개 모두 뽑았으면
			sum += S[two[0]][two[1]];
			return;
		}
		
		for(int i=0; i<N/2; i++) {
			if(visited[i]) continue;
			two[cnt] = numbers[i];
			perm(cnt+1, numbers);
			visited[i] = false;
		}
	}
}