문제

문제 링크

N개 팀중에서 N/2개를 뽑아 팀을 정하고 나머지 N/2명의 팀과 점수가 최소가 되게하는 문제다.

결국 핵심은 N개중에서 N/2를 뽑는것이다.
조합으로 생각해볼수 있을거같다.
python 을 사용했다면 combination을 사용했을테지만
C++로 라이브러리 사용없이 직접 구현해보았다.(c++도 순열과 조합을 표현하는 permutation이 있긴하다.)

처음 시도하였을때 너무도 자연스럽게 트리 아래로 내려간 다음
모든 가지를 체크하였다. 그랬더니 모든 가지를 방문해 중복이 굉장히 많이 생겼다.(너무 습관적으로 코딩하면 안될듯하다.)

다행히 시간 복잡도를 생각하다보니 잘못되었다는것을 알게되었다.
콤비네이션은 숫자를 뽑거나 안뽑거나 두가지 경우이므로
2^n이 된다. 그리고 각 말단 노드일때마다 base condition은 n^2 이된다.
그래서 n이 작은 경우에만 동작할듯 싶다.

나는 A팀을 먼저 뽑는 경우로 알고리즘을 작성했다.
이때 최대한 중복을 피하기위해
0번째는 항상 A팀에서 제외했다. 어차피 반대편 팀에 들어간다.

teamA[0]=false;

그러면 가지수가 절반이나 줄게된다.

또한 맴버수를 추가해도 목표치인 N/2에 도달하지 못하는 가지도 제거하였다.

if((memSize+(N-depth))<N/2) return;

이 방법은 다른 삼성 문제를 풀때 중요한 작업이여서 기억에 남는다.

근데 이 문제도 마지막에 틀렸습니다를 마주하였는데 원인은 isVisited같이 비트로 체크해주는데 int형으로 타입을 정하는 실수 때문에 그렇다.
(vsc로 코딩하는데 vsc에서는 문제를 항상 잡아주지 못한다..)

code

/**
 * 백준 14889
 * N개중에서 N/2를 뽑는 경우의 수(콤비네이션)
*/
#include <bits/stdc++.h>
#define MAX 1e9
using namespace std;

int N;
int graph[20][20];
int gap=MAX;
bool teamA[10]={false};

void check(){
    int scoreA=0;
    int scoreB=0;
    for(int i=0;i<N;i++){
        if(teamA[i]){
            for(int j=i+1;j<N;j++){
                if(teamA[j]){
                    scoreA+=graph[i][j];
                    scoreA+=graph[j][i];
                }
            }
        }
        else if(!teamA[i]){
            for(int j=i+1;j<N;j++){
                if(!teamA[j]){
                    scoreB+=graph[i][j];
                    scoreB+=graph[j][i];
                }
            }
        }
    }
    gap=(abs(scoreA-scoreB)<gap)?abs(scoreA-scoreB):gap;
    if(gap==0){
        cout<<0<<endl;
        exit(0);
    }
}
void pickMember(int depth,int memSize){
    if(memSize==N/2){
        // 점수 체크
        check();
        return;
    }
    if(memSize>N/2) return;
    // 가지치기
    if((memSize+(N-depth))<N/2) return;
    if(depth>=N) return;

    teamA[depth]=true;
    pickMember(depth+1,memSize+1);
    teamA[depth]=false;
    pickMember(depth+1,memSize);
}

int main(void){
    cin>>N;
    for(int i=0;i<N;i++){
        for(int j=0;j<N;j++) scanf("%d",&graph[i][j]);
    }
    
    // team 뽑기 combination (0번 사람은 항상 false, 절반만 해보면 되므로)
    teamA[0]=false;
    for(int i=1;i<=N/2;i++){
        teamA[i]=true;
        pickMember(i+1,1);
        teamA[i]=false;
        pickMember(i+1,0);
    }
    cout<<gap<<endl;
    return 0;
}