BOJ 14889 스타트와 링크

www.acmicpc.net/problem/14889

14889번: 스타트와 링크

문제 해결 전략

이 문제는 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;
}