[BOJ / C++] 14889 스타트와 링크 (삼성 기출)

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

문제풀이

N명의 사람 중, 스타트/링크로 나뉘어진 모든 조합을 구한 후 차이를 계산해서 그 중 제일 작은 것을 출력해야 한다.

조합을 구하기 위해 res배열을 0으로 초기화하고, 전형적인 조합 dfs를 사용하면서 2/N개의 원소를 1로 만들어준다.

🔗조합 구현 예시

총 2/N개가 선택되었을 때 res배열엔
2/N개의 1과 2/N개의 0이 있을 것이다.

1인 것을 스타트팀, 0인 것을 링크팀으로 하여 능력치 차이를 구해주면 된다.

📓 평소엔 조합을 구할 때 res배열의 크기를 뽑을 원소의 개수로 만들어놓고 res[level]=i 이런 형식으로 했는데, 이번엔 res배열의 크기를 전체 후보크기만큼 지정한 후 뽑힌 인덱스에 1을 넣어주는 것으로 구현했다. => 따라서 백트래킹 후 다시res[i]=0으로 만들어 줘야함!

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
#define MAX 2147000000

int minVal=MAX;
int N;
int map[21][21];
int res[20]; //스타트,링크 조합 1일 때 스타트

/* 능력치 차이 구하기*/
void computePower(){
    vector<int> start;
    vector<int> link;

    // 1인 것이 스타트팀!
    for(int i=1;i<=N;i++){
        if(res[i]==1) start.push_back(i);
        else link.push_back(i);
    }

    int startScore=0;
    int linkScore=0;

    for(int i=0;i<N/2;i++){
        for(int j=0;j<N/2;j++){
            if(i==j) continue;
            startScore+=map[start[i]][start[j]];
            linkScore+=map[link[i]][link[j]];
        }
    }

    int diff=abs(startScore-linkScore);
    minVal=min(diff,minVal);
}

/* N/2명의 조합 구하기.*/
void selectStart(int start,int level){
    if(level==N/2){
        // N/2명 골랐을 때 능력치 차이를 구한다.
        computePower();
        return;
    }

    for(int i=start;i<=N;i++){
        if(!res[i]){
            res[i]=1; //1로 설정한 것이 스타트팀.
            selectStart(i+1, level+1);
            res[i]=0;
        }

    }
}

int main(){
    cin>>N;
    for(int i=1;i<=N;i++){
        for(int j=1;j<=N;j++){
            cin>>map[i][j];
        }
    }

    //1. N/2 명의 스타트팀을 고른다. (조합)
    selectStart(1,0);
        //2. N/2명 골랐을 때 능력치 차이를 구한다.

    //능력치 차이의 최소값
    cout<<minVal<<"\n";
    return 0;
}