스타트와 링크 (14889)

1. 문제

문제 링크

2. 풀이

DFS를 이용해서 모든 팀원 조합을 구한 다음
그 차이의 최솟값을 구하는 문제입니다.

보통 DFS를 설계할 때
답을 재귀호출하면서 만들어나갈지,
답을 기저사례에서 계산할지 고민을 하는데
이 문제의 경우 후자의 방법을 이용하는 게 좋습니다.

왜냐하면 모든 팀원 조합을 알아야지만 그 팀원의 능력치를 계산할 수 있기 때문이죠.

그러면 재귀호출로 모든 팀원의 조합을 구해봅시다.
이 때 영리하게 스타트팀 팀원의 조합만 구하면 나머지는 링크팀 팀원의 조합일테니
스타트 팀원의 조합만 만들어 나갑시다.

스타트 팀원의 조합을 만드는 방법은

boolean[] isStartTeam = new boolean[N];

i번째 사람이 스타트 팀원 여부인지 체크하는 배열을 선언하고

for (int i = startIndex; i < N; i++) {
	isStartTeam[i] = true;
	ret = Math.min(ret, min(depth + 1, i + 1));
	isStartTeam[i] = false;
}

재귀 호출을 통해 모든 스타트 팀원을 만들어 나갑니다.

재귀 호출이 어떤 식으로 이루어지는지
N = 4일 때 그림으로 상세하게 보여드리자면

이런 식으로 이루어집니다.
그래서 (1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4) 가 스타트 팀원으로 뽑힙니다.
이런 트리를 만들어주기 위해
우리는 위 코드에서 startIndex로 현재 뽑은 i번째 사람의 다음 사람인 (i + 1)을 재귀 함수로 넘긴 겁니다.

이제 팀원을 나눴으면 스타트팀 팀원들의 능력치, 링크팀 팀원들의 능력치를 구하고
그 차이를 구하면 마무리가 되겠네요.

int startTeamAbility = 0; // 스타트팀 팀원들의 능력치
int linkTeamAbility = 0; // 링크팀 팀원들의 능력치
			
for (int i = 0; i < N; i++) {
	for (int j = 0; j < N; j++) {
		// 스타트팀 팀원들일 때
		if (isStartTeam[i] && isStartTeam[j]) {
			startTeamAbility += S[i][j];
		}
		// 링크팀 팀원들일 때
		else if (!isStartTeam[i] && !isStartTeam[j]) {
			linkTeamAbility += S[i][j];
		}
	}
}

// 두 팀의 능력치의 차이 
return Math.abs(startTeamAbility - linkTeamAbility);

총 정리를 해보면
1. 재귀호출로 스타트팀 팀원의 모든 조합을 구합니다.
2. 기저사례에서 스타트팀 능력치와 링크팀 능력치의 차이를 구합니다.
3. 그 중 가장 작은 값을 리턴합니다.

시간 복잡도는
경우의 수가 N명의 사람에서 (N / 2)명의 사람을 뽑는 경우의 수니까
N! / (2 x (N / 2)!) 개가 있고
각 경우의 수마다 팀의 능력치를 계산하는 로직은 N^2이 걸리니까
총 (N^2 x N!) / (2 x (N / 2)!) 이 됩니다.

3. 전체 코드

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

public class Main {
	
	static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
	static BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
	static int N;
	static int[][] S;
	static boolean[] isStartTeam;
	
	static int min(int depth, int startIndex) {
		// 2. 기저사례에서 스타트팀 능력치와 링크팀 능력치의 차이를 구합니다.
		if (depth == N / 2) {
			int startTeamAbility = 0; // 스타트팀 팀원들의 능력치
			int linkTeamAbility = 0; // 링크팀 팀원들의 능력치
			
			for (int i = 0; i < N; i++) {
				for (int j = 0; j < N; j++) {
					// 스타트팀 팀원들일 때
					if (isStartTeam[i] && isStartTeam[j]) {
						startTeamAbility += S[i][j];
					}
					// 링크팀 팀원들일 때
					else if (!isStartTeam[i] && !isStartTeam[j]) {
						linkTeamAbility += S[i][j];
					}
				}
			}
			
			// 두 팀의 능력치의 차이 
			return Math.abs(startTeamAbility - linkTeamAbility);
		}
		
		int ret = 987654321;
		
		// 1. 재귀호출로 스타트팀 팀원의 모든 조합을 구합니다.
		for (int i = startIndex; i < N; i++) {
			isStartTeam[i] = true;
			ret = Math.min(ret, min(depth + 1, i + 1));
			isStartTeam[i] = false;
		}
		
		// 3. 가장 작은 값을 리턴합니다.
		return ret;
	}
	
	public static void main(String[] args) throws Exception {
		N = Integer.parseInt(br.readLine());
		S = new int[N][N];
		isStartTeam = new boolean[N];
		
		for (int i = 0; i < N; i++) {
			StringTokenizer stk = new StringTokenizer(br.readLine());
			
			for (int j = 0; j < N; j++) {
				S[i][j] = Integer.parseInt(stk.nextToken());
			}
		}
		
		bw.write(min(0, 0) + "");
		bw.close();
	}
}

재귀 호출은 가장 작은 예시를 들어서 그림을 그려보는 습관이 중요합니다.