[C++] 백준 14889번: 스타트와 링크 (브루트 포스)

 

14889번: 스타트와 링크

---

문제 이해하기

 문제의 요구사항은 다음과 같습니다.

N명의 사람을 두 팀으로 나눌 때, 두 팀의 능력치 차이의 최솟값을 구하여라.

---

시간복잡도 어림하기

브루트포스 알고리즘

 N명의 사람을 두 팀으로 분류하는 모든 경우의 수를 계산하고, 각 경우의 능력치 차이를 구해 문제를 해결할 수 있습니다. n의 최댓값은 20이므로, 두 팀으로 분류하는 최대 경우의 수는 20C10 = 184756입니다. 또한, 능력치 배열의 최대 크기는 20 x 20 = 400이므로 총 반복 횟수는 184756 x 400 = 7천 정도 됩니다.

 

 7천 정도 반복 횟수는 연산량이 많아 보이지만, 각 시행에서 연산하는 것을 배열의 값을 합산하고, 그 차이를 구하는 단순 연산이므로 제한 시간 내에 문제를 해결하기 충분합니다.

 

 따라서 브루트포스 알고리즘을 통해 문제를 해결할 수 있습니다.

---

알고리즘 설계하기

 기본 아이디어는 다음과 같습니다.

1. 팀 분배
2. 각 팀의 능력치 합산
3. 능력치 차이 계산 및 최솟값 갱신

 

 가장 먼저 팀을 분배해야 합니다. 팀은 두 팀으로만 분배하면 되고, n의 최댓값이 20이므로 비트마스킹을 통해 구현할 수 있습니다. 팀을 의미하는 정수를 0부터 1 << 20 까지 반복하면서 1과 0의 개수가 같을 때 2번과 3번 코드를 실행하면 됩니다. 코드로는 다음과 같습니다.

for(int t = 1; t < (1 << n); t++){
        vector<int> v1, v2; //v1과 v2는 각 팀원의 인덱스를 저장
        for(int i = 0; i < n; i++){
            if(t & (1 << i)) v1.push_back(i);
            else v2.push_back(i);
        }
        if(v1.size() != n / 2) continue;
        
		/*능력치 계산 및 능력차 계산*/
    }

 

 팀을 분배한 이후에는 각 팀의 능력치를 합산해야합니다. 이는 능력치 배열을 탐색하면서 모두 더해주면 됩니다. 능력치 합산은 sum1, sum2와 같이 변수 두 개를 두고 나중에 차를 계산해도 되지만, 어차피 두 값의 차만 계산하면 되므로 팀1의 능력치는 더하고, 팀2의 능력치는 뺀 후 마지막에 abs 함수로 절댓값을 취하는 방식으로 구현하겠습니다.

 코드는 다음과 같습니다.

for(int i = 0; i < n / 2; i++){
    for(int j = 0; j < n / 2; j++){
       sum += a[v1[i]][v1[j]];
       sum -= a[v2[i]][v2[j]];
}

 다음과 같이 인덱스 기반 탐색을 통해 두 팀의 능력치를 한번에 탐색할 수 있습니다.

---

알고리즘 구현하기

 최종 코드는 다음과 같습니다.

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

int n, a[24][24], ret = 1e9;
int main(){
    cin >> n;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++) cin >> a[i][j];
    }
    
    for(int t = 1; t < (1 << n); t++){
        vector<int> v1, v2;
        /*팀 분배*/
        for(int i = 0; i < n; i++){
            if(t & (1 << i)) v1.push_back(i);
            else v2.push_back(i);
        }
        if(v1.size() != n / 2) continue; //팀 분배가 잘못된 경우

        int sum = 0;
        for(int i = 0; i < n / 2; i++){
            for(int j = 0; j < n / 2; j++){
                sum += a[v1[i]][v1[j]];
                sum -= a[v2[i]][v2[j]];
            }
        }
        ret = min(ret, abs(sum));
    }
    cout << ret;
    return 0;
}

 변수 t에 팀 배분 값이 담기고 이를 비트연산을 통해 v1과 v2에 팀원의 인덱스 값을 담습니다. 이후 각 팀의 능력치 차이를 sum 변수에 모두 담아 최솟값을 갱신합니다.

---