[백준 14889] 스타트와 링크

하루에 하나 알고리즘

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

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; }