스타트와 링크(백준 14889번)

문제

https://www.acmicpc.net/problem/14889

14889번: 스타트와 링크

알고리즘 풀이

1. 이차원 배열에 값을 입력받는다.

2. ck라는 boolean배열을 하나 만들어서 숫자를 뽑는 것을 체크한다.

3. 전체탐색을 해주면서 카운트를 1씩 올려준다.

4. 만약 카운트가 N의 절반이되면 팀이 반반으로 나뉜것이기 때문에 능력치를 비교해준다.

 

#include <iostream>
#include <cstring>
#include <vector>
#include <queue>
#include <algorithm>
using namespace std;
int N,Min = 987654321;
int ary[21][21];
bool ck[21] = {false};
void dfs(int cur,int cnt){
    if(cnt == N/2){
        int result2 = 0,result1 = 0;
        vector<int> start;
        vector<int> link;
        for(int i = 0;i<N;i++){
            if(ck[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){
                    result1 = result1+ary[start[i]][start[j]];
                    result2 = result2+ary[link[i]][link[j]];
                }
            }
        }
        int result = result1-result2;
        if(result<0){result = result*-1;}
        Min = min(result,Min);
        return;
    }
    else{
        for(int i = cur+1;i<N;i++){
            if(ck[i] == false){
                ck[i] = true;
                dfs(i,cnt+1);
                ck[i] = false;
            }
        }
    }
}
int main(int argc, char* argv[]){
    ios::sync_with_stdio(false);
    cin.tie(0); cout.tie(0);
    cin >> N;
    for(int i = 0;i<N;i++){
        for(int j = 0;j<N;j++){
            cin >> ary[i][j];
        }
    }
    dfs(0,0);
    cout << Min;
}