14889번: 스타트와 링크
예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다.
www.acmicpc.net
문제 해결 전략
이 문제는 n(짝수)명에서 2/n개를 고르고 이를 스타트 팀과 링크 팀으로 나눠 점수를 구하는 방식이다.
조합 방식으로 n/2개를 선택한 후에 각각 vector에 넣고, 이를 나누어 점수를 계산하였다.
소스
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
#define MAX 20
#define endl "\n"
int n;
int map[MAX][MAX];
bool check[MAX];
vector<int> start, link;
int minNum=9999;
void dfs(int cnt, int num){
if(cnt == n/2){
start.clear(); link.clear();
int startSum = 0, linkSum = 0;
for(int i = 0; i < n; i++){
if(check[i]){
start.push_back(i);
}else{
link.push_back(i);
}
}
for(int i = 0; i < start.size(); i++){
for(int j = 0; j < start.size(); j++){
if(i == j) continue;
startSum += map[start[i]][start[j]];
}
}
for(int i = 0; i < link.size(); i++){
for(int j = 0; j < link.size(); j++){
if(i == j) continue;
linkSum += map[link[i]][link[j]];
}
}
if(abs(startSum - linkSum) < minNum) minNum = abs(startSum - linkSum);
return;
}
for(int i = num; i < n; i++){
check[i] = true;
dfs(cnt + 1, i + 1);
check[i] = false;
}
}
int main(void){
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> n;
for(int i = 0; i < n; i++){
for(int j = 0; j < n; j++){
cin >> map[i][j];
}
}
dfs(0, 0);
cout << minNum;
}
'알고리즘과 자료구조 > 백준' 카테고리의 다른 글
BOJ 2018 수들의 합 5 (0) | 2020.10.26 |
---|---|
BOJ 11005 진법 변환 2 (0) | 2020.10.22 |
BOJ 16234 인구 이동 (0) | 2020.10.20 |
BOJ 17143 낚시왕 (0) | 2020.10.17 |
BOJ 19238 스타트 택시 (0) | 2020.10.17 |