[백준] 14889. 스타트와 링크 - 실버3

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

14889번: 스타트와 링크

 

문제 요약

입력으로 N과 N*N 배열에 들어가는 능력치가 주어진다. N/2명씩 스타트 팀, 링크 팀을 만들어서 팀에 속한 팀원끼리 만나면 발휘되는 능력치를 더하고, 두 팀의 능력치가 최소가 되는 값을 출력한다.

 

문제 해결 아이디어

당연히 처음에는 nCn/2의 문제라고 생각했다. 하지만 순열 조합 부분집합을 재귀로 구하는 문제의 쟁점은 가지치기! 즉 어떻게 최소한으로 돌릴 것인가를 생각해 봐야 한다.

생각해 보니 만약 n이 6이라고 한다면 1,2,3을 뽑는 것과 4,5,6을 뽑는 것은 같은 경우라는 걸 생각했다. 1,2,3이 스타트팀이 되든 링크팀이 되든 능력치의 최솟값을 구해야 하기 때문이다. 결국 경우의 수가 절반이 줄어들 수 있는 것이다. 이걸 식으로 구현하려면 첫번째 팀원을 무조건 뽑아 놓고 n-1명 중 n/2-1명을 뽑는다. 자동적으로 뽑히지 않은 n/2명은 다른 팀이 되는 것이다. 결국 n-1Cn/2-1으로 줄일 수 있다.

isSelected[] 배열을 만들어 뽑힌 팀원은 true, 뽑히지 않은 팀원은 false로 값을 주고, 처음에 isSelected[0]은 무조건 true로 설정해 둔다. 이 팀원이 뽑혔는지, 뽑히지 않았는지만 보면 되기 때문에 범위는 조합처럼 start 매개변수로 조절해 주고 isSelected[i] = true와 isSelected[i] = false의 경우 둘 다 체크했다.

 

완성된 코드

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

public class Main_BOJ_14889_스타트와링크 {
	static int N;
	static int[][] input;
	static boolean[] isSelected;
	static int min;

	public static void main(String[] args) throws Exception {
		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		N = Integer.parseInt(br.readLine());
		input = new int[N][N];
		isSelected = new boolean[N];
		isSelected[0] = true;
		min = Integer.MAX_VALUE;

		for (int i = 0; i < N; i++) {
			StringTokenizer st = new StringTokenizer(br.readLine(), " ");
			for (int j = 0; j < N; j++) {
				input[i][j] = Integer.parseInt(st.nextToken());
			}
		}
		pick(0, 1);
		System.out.println(min);
	}// end of main

	public static void pick(int cnt, int start) {
		if (cnt == (N / 2 - 1)) {
			int startTeam = 0; // true는 startTeam, false는 linkTeam이라고 가정. 반대가 되어도 상관없음 어차피 차이를 구하는 것이기 때문에
			int linkTeam = 0;
			for (int i = 0; i < N; i++) {
				if (isSelected[i]) { // i번째 선수가 start팀이라면
					for (int j = 0; j < N; j++) {
						if (isSelected[j]) // 또 다른 start팀을 찾아 떠난다
							startTeam += input[i][j];
					}
				} else { // i번째 선수가 link 팀이라면
					for (int j = 0; j < N; j++) {
						if (!isSelected[j]) // link 팀을 찾아 떠난다
							linkTeam += input[i][j];
					}
				}
			}

			min = Math.min(min, Math.abs(startTeam - linkTeam));
			return;
		}

		for (int i = start; i <= N - 1; i++) {
			isSelected[i] = true;
			pick(cnt + 1, i + 1);
			isSelected[i] = false;
		}
	}
}// end of class

 

여담이지만 이걸 대학교 3학년 때 학교에서 학기 다 끝나고 알고리즘 교수님이 풀어 보라고 주신 적이 있다.... 그때는 내가 직업을 개발자로 정할지 말지도 아무 생각이 없던 시절이었고 그냥 얼레벌레 학교 다니다가 알고리즘도 당연히 얼레벌레 수강했다. 학기 끝나고 식충이처럼 밤새 놀고 새벽 여섯 시에 자던 시절 갑자기 어? 나 공부나 해볼까? ㅋ 하고 새벽 4시쯤 잠 안 와서 자의로 알고리즘 문제를 풀었던 게 이 문제였다. 두시간? 세시간? 걸렸던 것 같다. 일곱시에 해가 뜨면서 코드를 완성시켰는데 그 기분이 아직도 생각난다. 나 어쩌면 개발자가 될 수도....? 꽤나 잘하는 걸 수도...? ㅋ 이런 생각 들었던 것 같다. 아직 그 코드가 남아 있어서 다 풀고 봤는데 정말 가관이었다 ㅋㅋㅋㅋㅋ 물론 그 이후로 알고리즘 문제는 다시 풀지도 않았고 그냥 프론트 백 기술 배우기 바빴는데 어쨌든 그때의 경험이 지금 이렇게 키보드 두드리게 만든 거 같다. 어쨌든 무서워하지 않고 다시 알고리즘에 도전하고 있으니까 말이다.