스타트와 링크 (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();
}
}
재귀 호출은 가장 작은 예시를 들어서 그림을 그려보는 습관이 중요합니다.
Author And Source
이 문제에 관하여(스타트와 링크 (14889)), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@front/백준-스타트와-링크-14889저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)