[백준/BOJ] 14889번 스타트와 링크 (C/C++)

백준 온라인 저지(BOJ) 14889번 스타트와 링크

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

14889번: 스타트와 링크

* 사용언어 : C언어, C++

 

1. 문제

N(짝수)명의 사람을 두 개 팀으로 나눔

i번 사람과 j번 사람이 팀이 되면 Sij + Sji 만큼 팀 능력치가 올라감

두 개 팀의 능력치의 차이가 최소가 되도록 팀을 구성하고 그 차이를 출력

 

2. 풀이

DFS를 활용하여 depth가 N / 2가 될 때까지 한 팀으로 구성합니다.

base condition에 도달한 경우 팀이 나눠진 것이니 두 팀의 Score를 구하고 차이(diff)를 구합니다.

 

단순한 DFS 구조로 푸는 문제지만 일반적인 형태로 구현하면 시간 초과가 발생합니다.

시간 초과를 해결하려면 DFS를 반복할 때 번호의 오름차순으로만 팀을 구성하게 하면 됩니다.

 

만약 오름차순이 아닌 전체로 탐색한다면 (1, 3, 6)이 팀인 경우의 점수를 이미 계산했는데

(1, 6, 3), (3, 1, 6), (3, 6, 1), (6, 1, 3) , (6, 3, 1)에서 같은 계산을 반복하게 됩니다.

 

따라서 불필요한 중복 계산이 발생하지 않도록 오름차순으로만 동작하게 하면 됩니다.

저는 방금 팀으로 넣은 사람의 번호를 dfs에 넣어주어, 해당 번호 다음부터 팀을 구성하게 했습니다.

 

3. 코드

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif
/*
14889_스타트와 링크
1112KB	120ms
*/
#include <cstdio>

const int LM = 20;
int s[LM][LM], N, n, teamId[LM], diff = 990;

void makeTeam(int depth, int prev) {
	if (depth == n) {
		int ts = 0, tl = 0;
		for (int i = 0; i < N; ++i) {
			for (int j = 0; j < N; ++j) {
				if (teamId[i] == teamId[j]) {
					if (teamId[i]) ts += s[i][j];
					else tl += s[i][j];
				}
			}
		}

		int diffNew = ts > tl ? ts - tl : tl - ts;
		if (diffNew < diff) diff = diffNew;
	}

	for (int i = prev + 1; i < N; ++i) {
		if (teamId[i]) continue;
		teamId[i] = 1;
		makeTeam(depth + 1, i);
		teamId[i] = 0;
	}
}

int main() {
#ifdef _WIN32
	freopen("input.txt", "r", stdin);
#endif // _WIN32
	scanf("%d", &N);
	for (int i = 0; i < N; ++i) {
		for (int j = 0; j < N; ++j) {
			scanf("%d ", &s[i][j]);
		}
	}
	n = (N >> 1);
	makeTeam(0, -1);
	printf("%d\n", diff);
	return 0;
}

* 문제 조건에 따라 팀 능력치 차이의 최대값은 990입니다. (100*10 - 1*10)