입력 : 축구 인원 N과 능력치 테이블
출력 : 팀을 구성하는 경우의 수 중에서 두 팀 간의 능력치차이가 제일 적을 경우의 능력치 차이 값
풀이
1. 한 팀을 만드는 모든 경우의 수를 재귀함수를 통해 구한다.
-> 재귀실행 1회 당 선수 1명 영입
-> 재귀실행 N/2회 실행시(기저조건), teamA에 인원이 N/2명이면 팀 능력치 계산
-> teamA에 없는 선수를 teamB에 영입해 능력치 계산 후 차이를 계산해 리턴
2. 중복을 피하기 위해 i번 선수 영입 후 다음 영입 선수는 i+1이상의 선수 중에서 선택
소스코드
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
63
64
65
66
67
68
69
70 |
#include <iostream>
#include <cmath>
#include <vector>
using namespace std;
int table[22][22];
bool teamCache[22];
vector<int> teamA;
int n;
int getTeamScore(){
int scoreA = 0;
int scoreB = 0;
vector<int> teamB;
for(int i=0; i<n; i++)
if(!teamCache[i])
teamB.push_back(i);
for(int i=0; i<n/2; i++){
for(int j=i+1; j<n/2; j++){
scoreA += table[teamA[i]][teamA[j]];
scoreA += table[teamA[j]][teamA[i]];
scoreB += table[teamB[i]][teamB[j]];
scoreB += table[teamB[j]][teamB[i]];
}
}
return abs(scoreA-scoreB);
}
int matching(int teamNum, int bottom){
if(teamNum == n/2){
if(teamA.size() != n/2)
return 10000000;
else
return getTeamScore();
}
int result = 10000000;
for(int i=bottom; i<n; i++){
int temp = 0;
teamA.push_back(i);
teamCache[i] = true;
temp = matching(teamNum + 1, i+1);
if(result > temp)
result = temp;
teamA.pop_back();
teamCache[i] = false;
}
return result;
}
int main() {
cin>>n;
for(int i=0; i<n; i++)
for(int j=0; j<n; j++)
cin>>table[i][j];
cout<<matching(0,0)<<endl;
return 0;
}
|
cs |
'개발 > 알고리즘' 카테고리의 다른 글
백준 알고리즘 14891 (0) | 2019.02.20 |
---|---|
백준 알고리즘 1673 (0) | 2019.02.20 |
백준 알고리즘 14500 (0) | 2019.02.19 |
백준 알고리즘 14501 (0) | 2019.02.16 |
백준 알고리즘 13458 (0) | 2019.02.16 |