[BAEKJOON] 14889번 스타트와 링크

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

14889번: 스타트와 링크

문제조건

1. n명의 사람을 각각 n/2 명씩 두팀으로 나눈다.
2. 한 팀의 능력치는 (i, j) 가 같은 팀이라면 map[i][j] + map[j][i]로 나타내고, 같은 팀의 사람들의 능력치를 모두더한다.
3. 두 팀의 능력치 차이의 최솟값은?

접근방법

 

보자마자 입력값도 작고, 최솟값을 구하기 위해 모든 경우의 수를 Brute Force로 탐색하면 되는 거 아닌가? 생각이 들었고, DFS로 모든 경우의 수에 대해서 탐색했다.

너무 쉬운데? (불안)

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int n, map[21][21], visited[21];
//능력치의 최소차이
int res;

void dfs(int cnt) {
	if (cnt == n / 2) {
		int half = 0, half2 = 0;
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if(visited[i] == 1 && visited[j] == 1) half += map[i][j];
				if (visited[i] == 0 && visited[j] == 0) half2 += map[i][j];
			}
		}
		res = min(res, abs(half-half2));
		return;
	}
	for (int i = 1; i < n; i++) {
		if (!visited[i]) {
			visited[i] = 1;
			dfs(cnt + 1);
			visited[i] = 0;
		}
	}
}
int main(){
	cin >> n;
	res = 9999;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> map[i][j];
		}
	}
	dfs(0);
	cout << res;
}

역시는 역시인가,,, 그냥 좀 쉬웠다고 느껴도 맞았다고 떠주면 안되나,,,ㅎㅎㅎ

 

---

시간 복잡도를 줄이기 위해서 생각해본것은, 이 문제는 두 팀에 능력치의 수를 다르게 주는것이 목적이 아닌, 차이가 가장 작은 경우만 구하면 된다는 것이다. 

ex) (10, 20)이 있다면, (20, 10)은 생각안해줘도 된다는 말!

그러니 중복된 값을 계산하는 과정을 생략해준다면 시간을 단축 시킬수 있다.

 

소스코드

#include <iostream>
#include <math.h>
using namespace std;
int n, map[21][21], visited[22];
//능력치의 최소차이
int res = 1000000000;

void dfs(int cnt, int idx) {
	if (cnt == n / 2) {
		int half = 0, half2 = 0;
		for (int i = 1; i <= n; i++) {
			for (int j = 1; j <= n; j++) {
				if(visited[i] == 1 && visited[j] == 1) half += map[i][j];
				if (visited[i] == 0 && visited[j] == 0) half2 += map[i][j];
			}
		}
		res = min(res,abs(half - half2));
		return;
	}
	for (int i = idx; i < n; i++) {
		visited[i] = 1;
		dfs(cnt + 1, i + 1);
		visited[i] = 0;
	}
}
int main(){
	cin >> n;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= n; j++) {
			cin >> map[i][j];
		}
	}
	dfs(0, 1);
	cout << res;
}

여기서 핵심부분은 dfs를 진행할때, for(int i = idx; i < n; i++) 으로 돌려주는 부분이다.

i <= n 으로 하지 않은 이유는 i == n일때, 두 그룹간의 숫자만 바뀔 뿐 두 그룹간의 차이는 동일하기 때문에 한번 차이를 구한것은 다시 안구하려고 한것이다.

제출한 것으로 n을 포함한것과 포함 안 시킨것의 차이는 어마어마 하다.