문제출처 : https://www.acmicpc.net/problem/14889
1. 문제요약
- 총 N명의 사람을 N/2 명씩 팀을 나눔
- 사람 번호를 1, 2, 3, 4라 했을때, 팀 1은 1, 2 / 팀 2는 3, 4
- 팀 능력치는 s[1][2] + s[2][1]
s[3][4] + s[4][2] 이다.(s[1][2], s[2][1]은 서로 다를 수 있다.)
- 팀 능력치 차이가 최소값은?
- 4 <= N <= 20 (N은 짝수)
2. 접근방법
- 한명의 사람이 스타트팀인지 링크 팀인지 구분
- 2^N
3. 시간복잡도
- 2^N
4. 회고
- 난 팀 능력치 계산을 팀을 만들 때 마다 하게 했는데...(사실 재귀를 거치면서 합산하면 된다고 생각은 했지만, 구현을 못했음)
- 그냥 for문으로 선택된 팀원이 i 이미 팀은 팀원을 1, 2 라 하면 sum += s[i][j] + s[j][i]; 하면 되는데...
- 스타트팀 : 1, 2 / 링크팀 : 3, 4 인 경우와
스타트팀 : 3, 4 / 링크팀 : 1, 2 인 경우는 팀 능력치 차이가 같다.
- 난 이걸 해결 못해서 그냥 모든 경우(2^N)으로 해결했다.
- 해결하는 가장 쉬운 방법은 그냥 1을 한팀에 고정시키면 된다.
- next_permutation으로 4명이면 0 0 1 1을 순열로 만들어서 0 인경우 A팀 1 인경우 B팀으로 구분시키는 방법도 있음
- 사람을 순열돌리는 것보다 시간이 빠르며 최악 20! / 10! * 10! = 190,000
소스코드
#include<iostream>
using namespace std;
int n, s[21][21], teamA[21], teamB[21], ans = 987654321;
int abs(int a){
return ((a < 0) ? -a : a);
}
int calScore(int team[21]){
int temp = 0;
for (int i = 0; i < n / 2 - 1; i++){
for (int j = i + 1; j < n / 2; j++){
temp += s[team[i]][team[j]] + s[team[j]][team[i]];
}
}
return temp;
}
void dfs(int num, int cnt_a, int cnt_b){
if (cnt_a == n / 2 && cnt_b == n / 2){
int score_a = calScore(teamA);
int score_b = calScore(teamB);
if (abs(score_a - score_b) < ans)
ans = abs(score_a - score_b);
return;
}
// teamA
if (cnt_a < n / 2){
teamA[cnt_a] = num;
dfs(num + 1, cnt_a + 1, cnt_b);
}
// teamB
if (cnt_b < n / 2){
teamB[cnt_b] = num;
dfs(num + 1, cnt_a, cnt_b + 1);
}
}
int main(void){
cin >> n;
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
cin >> s[i][j];
dfs(1, 0, 0);
cout << ans << "\n";
return 0;
}
[출처 : BOJ, 문제에 대한 모든 권리는 BOJ(acmicpc.net, startlink)에 있음]