[백준/c++] 15661번: 링크와 스타트

 

 

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

15661번: 링크와 스타트

 

백트래킹으로 구현하면 되는데, 스타트팀이나 링크팀에 최소 한 명은 들어가야 한다.

그런데 1명만 들어가면 능력치를 구할 수 없다. 그러므로 2명부터~n-3명까지를 한 팀에 넣을 수 있다. 

for(int i=2; i<n-1; i++) BT(0, 0, i);

 

BT 마지막 인자로 들어간 것은 스타트팀에 들어갈 멤버 수다. 

BT를 돌면서 member 값이 되면 compareStartLink()함수로 들어가서 둘의 능력치 차이 값을 구한다.

중복을 피하기 위해 check 배열을 통해 걸러주고, 이 배열로 스타트팀에 들어갔는지 링크팀에 들어갔는지 체크할 수도 있다. 

(true면 start team, false면 link team)

void BT(int cnt, int s, int member){
    if(cnt == member){
        compareStartLink();
        return;
    }
    
    for(int i=s; i<n; i++){
        if(!check[i]){
            check[i] = true;
            BT(cnt+1, i+1, member);
            check[i] = false;
        }
    }
}

 

compareStartLink()함수에선 3가지 작업이 이루어진다.

1. check배열 속 true면 start팀에 넣어주기 / false면 link팀에 넣어주기 → 각 팀에 멤버 번호 들어감

2. 이중 for문돌면서 i번째 팀원과 j번째 팀원의 능력치 추가 

3. 팀 능력 차이 최솟값 구하기

 

void compareStartLink(){
    vector<int> start, link;
    int sAB = 0, lAB = 0;
    
    //1
    for(int i=0; i<n; i++){ 
        if(check[i]) start.push_back(i);
        else         link.push_back(i);
    }
    
    //2
    for(int i=0; i<start.size(); i++){
        for(int j=i+1; j<start.size(); j++){
            sAB += (s[start[i]][start[j]] + s[start[j]][start[i]]);
        }
    }
    for(int i=0; i<link.size(); i++){
        for(int j=i+1; j<link.size(); j++){
            lAB += (s[link[i]][link[j]] + s[link[j]][link[i]]);
        }
    }
    
    //3
    ans = min(ans, abs(sAB - lAB));
}

 

---

[전체코드]

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
int n, s[21][21], ans = 40001;
bool check[21];

void compareStartLink(){
    vector<int> start, link;
    int sAB = 0, lAB = 0;
    
    for(int i=0; i<n; i++){ //check를 보고 체크했으면 start, 안했으면 link
        if(check[i]) start.push_back(i);
        else         link.push_back(i);
    }
    
    for(int i=0; i<start.size(); i++){
        for(int j=i+1; j<start.size(); j++){
            sAB += (s[start[i]][start[j]] + s[start[j]][start[i]]);
        }
    }
    for(int i=0; i<link.size(); i++){
        for(int j=i+1; j<link.size(); j++){
            lAB += (s[link[i]][link[j]] + s[link[j]][link[i]]);
        }
    }
    
    ans = min(ans, abs(sAB - lAB));
}

void BT(int cnt, int s, int member){
    if(cnt == member){
        compareStartLink();
        return;
    }
    
    for(int i=s; i<n; i++){
        if(!check[i]){
            check[i] = true;
            BT(cnt+1, i+1, member);
            check[i] = false;
        }
    }
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n;
    for(int i=0; i<n; i++) for(int j=0; j<n; j++) cin >> s[i][j];
    for(int i=2; i<n-1; i++) BT(0, 0, i);
    cout << ans << '\n';
    return 0;
}