알고리즘 문제풀이/백준

[백준 14889] 스타트와 링크

홍시홍 2019. 2. 14. 08:49

하루에 하나 알고리즘

누군가에게 조금이라도 도움이 됫으면 하는 바램으로 이 글을 작성합니다


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


요구사항

1. 스타트와 링크 팀 나누기(스타트팀 절반, 링크 팀 절반)

2. 반반 씩 나누어 졌으면 스타트 팀 합 - 링크팀 합의 최소 구하기


풀이

1 풀이

dfs로 깊이가 n이 될때 고른 수가 n/2가 가 될 수 있도록 한다.

2 풀이

스타트 팀 합 과 링크 팀 합을 구하여 두개의 차의 최소를 구한다


답

최소가 답이 되도록 한다.


소스 코드


1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
#include <iostream>
#include <algorithm>
using namespace std;

int n;
int map[21][21];
int visit[21];
int ans = 987654321;
void solve(int cnt,int go)
{

	if (cnt == n)
	{
		if (go == n / 2)
		{
			int start = 0;
			int link = 0;
			int suma = 0;
			for (int i = 0; i < n; i++)
			{
				for (int j = 0; j < n; j++)
				{
					if (visit[i] == 1 && visit[j] == 1)
					{
						start = start + map[i][j];
					}
					if (visit[i] == 0 && visit[j] == 0)
					{
						link = link + map[i][j];
					}
				}
			}
			suma = abs(start - link);
			ans = min(ans, suma);
			return;
		}
		return;
	}
		visit[cnt] = 1;
		solve(cnt + 1, go + 1);
		visit[cnt] = 0;
		solve(cnt + 1, go);

}
int main()
{
	cin >> n;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < n; j++)
		{
			int x;
			cin >> x;
			map[i][j] = x;
		}

	}

	solve(0,0);
	cout << ans << endl;
	return 0;
}