[Gold 5] 15661 링크와 스타트

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

15661번: 링크와 스타트

 

이 문제는 조합을 이용한 완전 탐색 문제이다.

 

팀은 2개로 이루어져 있고, 팀의 최소 인원은 2명이다.

따라서 2명의 묶음이 만들어 졌을 때 팀원의 능력치를 더한 후

2개의 팀간의 능력치 차이의 절대 값을 구하면 된다.

 

팀 간의 묶음은 다음과 같다.

1 1 1 1 
1 1 1 0 
1 1 0 1 
1 1 0 0 
1 0 1 1 
1 0 1 0 
1 0 0 1 
1 0 0 0 
0 1 1 1 
0 1 1 0 
0 1 0 1 
0 1 0 0 
0 0 1 1 
0 0 1 0 
0 0 0 1 
0 0 0 0

이중 최소 값은 2개의 팀 간의 능력치 합이 최소인 경우에만 가능하고 1팀에 3명이 몰리는 순간은 모두 최소가 아니게 된다.

따라서 팀간에 균형있게 만들어졌는지는 판단하지 않아도 된다. 

 

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

int N;
int ability[21][21];
bool visited[21];
int result = 987654321;

int calc(){
    int counter1 = 0;
    int counter2 = 0;
    for(int i = 0;i<N-1;i++){
        for(int j = i+1;j<N;j++){
            if(visited[i] && visited[j])
                counter1 += ability[i][j] + ability[j][i];
            
            else if(!visited[i]&&!visited[j])
                counter2 += ability[i][j] + ability[j][i];
        }
    }
    return abs(counter1- counter2);
}

void combination(int counter){
    if(counter==N){
        result = min(result, calc());
        return;
    }
    visited[counter] = true;
    combination(counter+1);
    visited[counter] = false;
    combination(counter+1);
}

int main() {
	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>>ability[i][j];
    }
    combination(0);
	cout<<result<<'\n';

	return 0;
}