(C++) - 백준(BOJ) 15661번 : 링크와 스타트

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

15661번: 링크와 스타트

backtracking을 이용한 brute force였습니다.

 

 

📕 풀이방법

최대 20명입니다. 팀은 두 개로 나뉘므로 한쪽의 인원이 정해진다면 나머지는 자동으로 정해집니다. 따라서 20C1 ~ 20C10로 팀을 뽑아서 능력치를 확인하면 됩니다. 20C10는 184756이므로 시간제한 2억안에 수행가능합니다.

 

📔 입력 및 초기화

 각 인원의 능력치 정보를 입력받아 ability라는 2차원 배열 변수에 저장합니다.

 

 

📔 풀이과정

 1. 한쪽에 뽑는 인원수를 1 ~ n/2까지 loop를 돌며 뽑아줍니다. 

 2. 조합으로 결정된 인원에 따라 teamA, teamB로 나눠줍니다.

 3. 이후 각 팀의 능력치를 구한 뒤 그 최소를 int형 변수 ans에 저장합니다.

 

 

📔 정답출력

ans를 출력합니다.

---

 

 

📕 Code

#include <bits/stdc++.h>
using namespace std;
int n, ans = 0x3f3f3f3f, people[21], ck[21], ability[21][21];
vector <int> teamA, teamB;

void pickTeam(int depth, int idx,int pickNum){
    if(depth == pickNum){
        teamA.clear();
        teamB.clear();

        for(int i = 0; i < n; i++){
            if(people[i]) teamA.push_back(i);
            else teamB.push_back(i);
        }

        int a = 0, b = 0;

        for(int i = 0; i < teamA.size(); i++){
            for(int j = 0; j < teamA.size(); j++){
                a += ability[teamA[i]][teamA[j]];
            }
        }

        for(int i = 0; i < teamB.size(); i++){
            for(int j = 0; j < teamB.size(); j++){
                b += ability[teamB[i]][teamB[j]];
            }
        }
        
        ans = min(ans,abs(a-b));
        return;
    }
    
    for(int i = idx; i < n; i++){
        if(ck[i]) continue;
        ck[i] = 1;
        people[i] = 1;
        pickTeam(depth + 1, i + 1, pickNum);
        people[i] = 0;
        ck[i] = 0;
    }
}


int main(){
    cin >> n;
    for(int i = 0; i < n; i++){
        for(int j = 0; j < n; j++){
            cin >> ability[i][j];
        }
    }

    //i명 뽑는다. 1팀 : i, 2팀 : n-i명
    for(int i = 1; i <= n/2; i++){
        memset(ck,0,sizeof(ck));
        pickTeam(0,0,i);
    }
    cout << ans;
}