[구현 / BOJ 14889 / C++] 스타트와 링크

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

14889번: 스타트와 링크

1) nCn/2 를 구한다.
2) 두 팀을 나눈 경우의 수 각각에 대하여 능력치 합을 구한 다음, 그 차이를 구한다.
3) 그 차이가 가장 적은 경우가 답이 된다.

코드가 좀 더럽다...

이 문제의 핵심은 nCn/2 라는 점이다. 나는 이걸 그냥 combination으로 해결하려고 했다.

 

combi 함수를 선언하고 vector<int> now에는 그 조합이 나온다. 그리고나서 그 조합에 해당하는 n*n번의 과정으로 해당 팀원들의 한 쌍의 합을 구했다. 

 

여기서 문제는 다른 팀원들이다!!.. 그래서 난 어쩔 수 없이 vector<int> now를 완성하는 동안 bool 배열을 선언하여 어느팀원이 빠졌고, 들어갔는지 계속 체크해갔다. 그리고나서 그 빠진인원을 다 센 후 그 인원들로 이뤄진 팀의 능력치 합을 구했다.

 

그러다 보니 굉장히 중구난방으로 풀어버렸다. 코딩테스트 공부를 오랜만에 하니깐 진짜 머리가 백지 상태다 ㅠㅠ 어디서부터 복습해야할지 감도 안온다 ... ㅠㅠ

 

다시 화이팅하자!!

 

#include <bits/stdc++.h>

using namespace std;
int arr[20][20], N, res=INT_MAX;
bool bd[20];
vector<pair<int, int>> pv;

void combi(int st, vector<int> now){
    if(now.size()==N/2){
        int team1=0;
        int team2=0;
        vector<int> notnow;
        for(int i = 0 ; i < N; i++){
            if(!bd[i]) notnow.push_back(i);
        }
        
        for(int i = 0 ; i < notnow.size(); i++){
            for(int j = 0 ; j < notnow.size(); j++){
                team2+=arr[notnow[i]][notnow[j]];
            }
        }
        
        for(int i = 0 ; i < now.size(); i++){
            for(int j = 0 ; j < now.size(); j++){
                team1+=arr[now[i]][now[j]];
            }
        }
        
        res = min(res, abs(team1-team2));
        return;
    }
    
    for(int i = st+1 ; i < N ; i++){
        now.push_back(i);
        bd[i]=1;
        combi(i, now);
        now.pop_back();
        bd[i]=0;
    }
    
    return;
}



int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    
    cin >> N;
    
    for(int i = 0 ; i < N ; i++){
        for(int j = 0 ; j < N ; j++){
            cin >> arr[i][j];
        }
    }
    vector<int> v;
    combi(-1, v);
    
    cout << res;
    
    
}