[BOJ] 14889 스타트와 링크 - Java

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

14889번: 스타트와 링크

---

1. 문제

NxN크기의 map에 능력치 크기가 쓰여있다. N명 중 N/2명으로 각각 2개의 팀을 만들었을 때

각 팀이 가지는 능력치의 차이가 최소가 될 때의 최솟값을 출력한다.

능력치는 각 팀의 팀원 번호에 따라 결정된다.

팀원이 1, 2, 3일 경우

map[1][2] + map[2][1] + map[1][3] + map[3][1] + map[2][3] + map[3][2]

가 능력치가 된다.

2. 풀이

조합으로 풀었다.

조합으로 팀1의 구성원을 정하였다. 이 때 visited를 사용하여 팀1로 지정된 번호는 true로 방문표시하였고

comb가 끝나면 다시 false로 원복시켜주었다.

팀2는 visited가 false인 숫자로 구성하여 능력치를 구한 후

팀1의 능력치와 팀2의 능력치 차이 절댓값으로 매번 최솟값을 갱신해주어 답을 구하였다.

 

3. 코드

import java.io.*;
import java.util.*;

public class Main {
    
	static int N, map[][], ans, tgt[], tgt2[];
	static boolean visited[];
	
	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st = null;
		
		N = Integer.parseInt(br.readLine());
		
		map = new int[N][N];
		tgt = new int[N/2];
		visited = new boolean[N];
		
		for (int i=0; i<N; i++) {
			st = new StringTokenizer(br.readLine());
			for (int j=0; j<N; j++) {
				map[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		// 입력 끝
		
		ans = Integer.MAX_VALUE;
		comb(0, 0);
		System.out.println(ans);
	}
	
	static void comb(int tgtIdx, int start) {
		if (tgtIdx == N/2) {
			check();
			return;
		}
		for (int i=start; i<N; i++) {
			tgt[tgtIdx] = i;
			visited[i] = true;
			comb(tgtIdx+1, i+1);
			visited[i] = false;
		}
	}
	
	static void check() {
		int sum = 0;
		for (int i=0; i<N/2; i++) {
			for (int j=0; j<N/2; j++) {
				if (i==j) continue;
				int y = tgt[i];
				int x = tgt[j];
				sum += map[y][x];
			}
		}
		
		tgt2 = new int[N/2];
		int idx = 0;
		for (int i=0; i<N; i++) {
			if (visited[i]) continue;
			tgt2[idx] = i;
			idx++;
		}
		
		int sum2 = 0;
		for (int i=0; i<N/2; i++) {
			for (int j=0; j<N/2; j++) {
				if (i==j) continue;
				int y = tgt2[i];
				int x = tgt2[j];
				sum2 += map[y][x];
			}
		}

		int res = Math.abs(sum - sum2);
		ans = Math.min(ans, res);
	}
}

4. 사담

조합 문제는 뭔가 게임같다.