[백준] 14889번: 스타트와 링크

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

14889번: 스타트와 링크

 

문제 이해

음~ 쉽다 해놓고 이상한 오타내고서 헤맨 문제...ㅎㅎ

최대 20명을 두 팀으로 나누고서 점수 계산만 하면 되니까,

두 팀으로 나누는 게 핵심인 문제이다.

 

두 팀으로 나눈다 -> 선택 10명 vs 비선택 10명 이렇게 나누면 되겠다!

그러면 DFS로 10명을 고르는 조합을 구해주면 되겠다!

 

작성 코드

#include <stdio.h>
#include <string.h>
#define MAXN 20
#define ABS(x) (((x)>0)? (x):-(x))
// N/2 개를 골라서 한 팀하고, 다른 한 팀 정하면 됨 >> DFS

int N;
int map[MAXN + 5][MAXN + 5];
int sel[MAXN + 5];
int min_diff = 0x7fffffff;

void Get_Input(void) {
	scanf("%d", &N);
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			scanf("%d", &map[i][j]);
		}
	}
}

int Get_Min_Diff(void) {

	int t0=0, t1=0;
	for (int i = 1; i <= N; i++) {
		for (int j = 1; j <= N; j++) {
			if (i == j) continue;
			if (sel[i] == sel[j]) {
				// 같은 팀 -> 포인트 올라감
				if (sel[i] == 0) {
					t0 += map[i][j];
				}
				else {
					t1 += map[i][j];
				}

			}
		}
	}
	return ABS(t0 - t1);
}

void DFS(int cnt, int idx) {
	
	// 종료
	if (cnt == N / 2) {
		int res = Get_Min_Diff();
		if (res < min_diff) min_diff = res;
		return;
	}

	// 재귀
	for (int i = idx; i <= N; i++) {
		sel[i] = 1;
		DFS(cnt + 1, i+1);
		sel[i] = 0;
	}
}

int main(void) {
	Get_Input();
	DFS(0, 1);
	printf("%d", min_diff);
	return 0;
}