[삼성SW테스트] 백준 14889번 - 스타트와 링크 (정답률 50%)

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

14889번: 스타트와 링크

삼성 SW테스트 기출 문제다.

브루트포스 문제로 단순 순열 문제로 바꿔 풀 수 있다.

최적화 안하고 그냥 풀어도 10분도 안걸리는 문제.

 

#include <iostream>
#include <vector>
#include <algorithm>
#define INF 987654321
using namespace std;
int N;
int answer = INF;
vector<vector<int> > ability; // 모든 사람들의 능력치 저장.
vector<int> flag;
vector<int> teamA, teamB;
 
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    
    cin >> N;
    ability.assign(N, vector<int>(N, 0));
 
    for (int i = 0; i < N; i++){
        for (int j = 0; j < N; j++){
            cin >> ability[i][j];
        }
    }
 
    for (int i = 0; i < N / 2; i++){
        flag.push_back(0);
        flag.push_back(1);
    }
    sort(flag.begin(), flag.end());
    int sum_A = 0, sum_B = 0;
    do{
        for (int i = 0; i < N; i++){
            if (flag[i] == 0){
                teamA.push_back(i);
            }
            else
                teamB.push_back(i);
        }
 
        for (int i = 0; i < teamA.size(); i++){
            int left = teamA[i];
            for (int j = 0; j < teamA.size(); j++){
                if (i == j)continue;
                int right = teamA[j];
                sum_A += ability[left][right];
            }
        }
 
        for (int i = 0; i < teamB.size(); i++){
            int left = teamB[i];
            for (int j = 0; j < teamB.size(); j++){
                if (i == j) continue;
                int right = teamB[j];
                sum_B += ability[left][right];
            }
        }
 
        answer = min(answer, abs(sum_A - sum_B));
        sum_A = 0, sum_B = 0;
        teamA.clear();
        teamB.clear();
    } while (next_permutation(flag.begin(), flag.end()));
 
    cout << answer << '\n';
    return 0;
}