728x90
반응형
이 문제는 재귀 문제이다.
사람을 스타트팀에 넣는 경우, 링크 팀에 넣는 경우로 재귀 함수를 구현한다.
스타트팀에 구성된 인원 수 : n/2
링크 팀에 구성된 인원 수: n/2
가 아닌 경우도 포함되겠지만,
N(4 ≤ N ≤ 20, N은 짝수) 이므로 2초를 넘을 위험은 없다.
start.push_back(index);
permutation(index + 1);
start.pop_back();
link.push_back(index);
permutation(index + 1);
link.pop_back();
스타트팀과 링크팀에 구성된 인원 수가 n/2로 채워졌을 때,
능력치를 더하고, 가장 능력치 차가 나지 않는 경우의 수를 저장한다.
if(index == n){
if(start.size() ==n / 2 && link.size() == n / 2){
int sum = 0;
for(int i = 0; i < start.size() - 1; i++){
for(int j = i + 1; j < start.size(); j++){
if(i == j) continue;
sum += score[start[i]][start[j]] + score[start[j]][start[i]];
sum -= score[link[i]][link[j]] + score[link[j]][link[i]];
}
}
answer = min(answer, abs(sum));
}
return;
}
코드는 이렇다.
//스타트와 링크
#include <iostream>
#include <vector>
#include <math.h>
using namespace std;
int score[20][20];
int n;
int answer = 987654321;
vector<int> start;
vector<int> link;
void permutation(int index){
if(index == n){
if(start.size() ==n / 2 && link.size() == n / 2){
int sum = 0;
for(int i = 0; i < start.size() - 1; i++){
for(int j = i + 1; j < start.size(); j++){
if(i == j) continue;
sum += score[start[i]][start[j]] + score[start[j]][start[i]];
sum -= score[link[i]][link[j]] + score[link[j]][link[i]];
}
}
answer = min(answer, abs(sum));
}
return;
}
start.push_back(index);
permutation(index + 1);
start.pop_back();
link.push_back(index);
permutation(index + 1);
link.pop_back();
}
int main(void){
cin >> n;
for(int i = 0; i < n; i++){
for(int j =0; j < n; j++){
cin >> score[i][j];
}
}
permutation(0);
cout << answer;
}
반응형
'algorithm' 카테고리의 다른 글
[algorithm] 백준 - 스도쿠 (0) | 2020.11.19 |
---|---|
[algorithm] 백준 - 숨바꼭질 2 (0) | 2020.11.17 |
[algorithm] 백준 - 단어수학 (0) | 2020.11.14 |
[algorithm] 백준 - 소인수분해 (0) | 2020.11.13 |
[algorithm] 백준 - 부분 수열의 합 2 (0) | 2020.11.10 |