백준 15661 링크와 스타트 C++

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

---

---

입력

첫째 줄에 N(4 ≤ N ≤ 20)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100보다 작거나 같은 정수이다.

---

출력

첫째 줄에 스타트 팀과 링크 팀의 능력치의 차이의 최솟값을 출력한다.

---

스타트팀과 링크팀으로 사람들을 나누는데, 두 팀의 인원수는 같지 않아도 되고, 1명 이상이어야 합니다.

능력치 Sij가 주어지는데, Sij는 i번 사람과 j번 사람이 같은 팀에 속했을 떄, 팀에 더해지는 능력치입니다.

 

스타트 팀과 링크팀으로 나눌 떄, 발생할 수 있는 인원의 수는 다음과 같습니다.

만약 N이 4라면, 

스타트 팀이 1명, 링크 팀이 3명

스타트 팀이 2명, 링크 팀이 2명

스타트 팀이 3명, 링크 팀이 1명, 총 3가지 경우가 발생합니다.

0부터 N-1까지 next permutation을 돌려서 스타트팀과 링크팀을 나누고 능력치의 차이의 최소를 구하였습니다.

---

#include <iostream>
#include <algorithm>
#include <vector>
#include <cmath>
using namespace std;

int map[21][21];
int n;
int ans = 987654321;

void init(){ //map[i][j]는 i과 j와 팀일떄 팀에 더해지는 능력치 
    cin >> n;
    for(int i = 0;i<n;i++){
        for(int j = 0;j<n;j++){
            cin >> map[i][j];
        }
    }
}

void permutation(){ //1부터 N-1까지 Next_permutation, combinate가 1이면 스타트 팀, 0이면 링크 팀 
    
    for(int i = 0;i<n-1;i++){
        vector<int> combinate;
        
        for(int j = 0;j<i;j++){ //스타트 팀 
            combinate.push_back(1);
        }
        for(int j = 0;j<n-i;j++){ //링크 팀 
            combinate.push_back(0);
        }
        sort(combinate.begin(),combinate.end()); 
        do{ 
            int start = 0;
            int link = 0;
            for(int i = 0;i<n;i++){
                for(int j = 0;j<n;j++){
                    if(i != j){ //스타트 팀의 능력치 
                        if(combinate[i] == 1 && combinate[j] == 1){
                            start += map[i][j];
                        }
                        //링크 팀의 능력치 
                        else if(combinate[i] == 0 && combinate[j] == 0){
                            link += map[i][j];
                        }
                    }
                }
            }
            //두 팀의 차이의 최소 값 갱신 
            if(abs(start-link) < ans){
                ans = abs(start-link);
            }
        }while(next_permutation(combinate.begin(),combinate.end()));
    }
}

int main(void){
    init();
    permutation();
    cout << ans;
}