[백준] 14889:스타트와 링크 C++ 풀이

14889: 스타트와 링크

 

 

문제 링크

해결 방법 

1. combination을 함수를 작성하여 n명의 사람을 n/2명의 두 팀으로 나누어 준다. (이 때 permutation으로 작성하면 안된다.)
   예를 들어 permutation은 team1: (1,2), team2: (3,4) 뿐만 아니라 team1:(2,1), team2:(3,4) 또는 team1:(2,1), team2:(4,3) 처럼 팀원을 팀안에서도 분할하게 되는데,  이 경우가 이번 문제에서는 결과적으로 같은 능력치를 갖기 때문이다. 순서를 주어서 조합으로 구현해야 한다.
2. cnt가 n/2가 되었다면 정확하게 visited배열의 절반 만이 true가 되었기 때문에 이 배열을 이용해 팀간의 능력치를 구해서 최솟값을 갱신해주면 된다.
3. 능력치를 구할 때는, 2중 for문을 이용하여 i와j에 해당하는 visited배열의 원소가 모두 true라면 arr[i][j]와 arr[j][i]를 team1(변수 a)에 더해주고, 둘 다 false라면 team2(변수 b)에 더해준다.
4. (team1 - team2)의 절댓값을 이용하여 최소인 ans를 찾아 출력한다.

#include <iostream>
#include <cmath>
using namespace std;
int arr[20][20];
bool visited[20];
int n;
int ans = 1234567890;
void combi(int cnt, int cur){
    if(cnt == n/2){
        int a = 0;
        int b = 0;
        // check 
        for(int i=0; i<n; i++){
            for(int j=i+1; j<n; j++){
                if(visited[i] && visited[j]){
                    a+= arr[i][j];
                    a+= arr[j][i];
                }else if(!visited[i] && !visited[j]){
                    b+= arr[i][j];
                    b+= arr[j][i];
                }
            }
        }
        ans = min(ans, abs(a-b));
    }
    for(int i=0; i<n; i++){
        if(visited[i]==false && i>cur){
            visited[i] = true;
            combi(cnt+1, i);
            visited[i] = false;
        }
    }
 
}
 
 
int main(){
    cin>>n;
    for(int i=0; i<n; i++){
        for(int j=0; j<n; j++){
            cin>> arr[i][j];
        }
    }
    combi(0,-1);
    cout <<ans<<endl;
 
}