[백준/BOJ] 14889번: 스타트와 링크 (백트래킹 기법) - C++ 문제풀이

 

문제 설명

 

문제 링크: https://www.acmicpc.net/problem/14889

 

풀이

한 그룹의 사람들 중에서 스타크와 링크 팀으로 나누어 각 팀의 능력치 차이의 최소 값을 출력하는 문제입니다.

 

짝수인 N 사람들 중에서 M=N/2 사람을 뽑아 팀을 만드는 것부터 해야겠네요.

편의상 팀명을 A팀이라고 하겠습니다.

주의할 점은 1번과 3번을 뽑는 것과 3번과 1번을 뽑는 것은 같은 것으로 봐야 한다는 거죠.

이 경우의 수를 제거하기 위해서, 다음 사람의 번호는 이전 사람의 번호보다 크도록 뽑았습니다.

void Pickup( int num, int start){

    if ( num == M){
        return;	// 팀에 필요한 사람을 뽑았음
    }

    int to = N - M + num;	// 다음 사람을 뽑을 수 있는 여유는 남긴다
    
    for(int i = start; i < to; i++){	// 이전에 뽑은 번호 다음부터 선택한다
    
        flags[i] = 1;   // selected
        
        Pickup(num+1, i+1);	// 다음 사람을 뽑는다

        flags[i] = 0;
    }
}

 

사람을 뽑는 방식은 백트래킹 기법에 기반을 두고 있습니다.

재귀적으로 다음 사람을 뽑는 과정이 끝나 팀을 구성한 후, 다시 이전 상태로 돌아와 다른 사람을 선택하는 과정을 통해 가능한 모든 팀을 만들 수 있습니다.

 

이제, 만들어진 팀의 능력치를 계산하면 되겠네요.

이 글에서는 모든 사람들 간의 능력치 총합을 계산한 후,  A팀의 멤버를 뽑을 때마다 이번에 뽑힌 사람과 A팀 사람들 간의 능력치는 더하고, 전체 능력치의 합에서 A팀이 아닌 멤버와의 능력치는 빼는 방식으로 계산했습니다.

그러면, totalS는 자연히 A팀이 아닌 팀의 능력치가 됩니다.

 

for( int i = 0; i < N-1; i++){		// N은 모든 사람의 수
    for( int j = i+1; j < N; j++){
        totalS += S[i][j] + S[j][i];	// 모든 사람과의 능력치의 총합을 구한다
    }
}

 

void Pickup( int num, int start){

    if ( num == M){	// A팀을 다 뽑았다
   
        minV = min( minV, abs(totalS-teamS1));	// 팀 간 능력치 차이의 최소값
        return;
    }

    int curTeamS1 = teamS1;
    int curTotalS = totalS;

    int to = N - M + num;
    for(int i = start; i < to; i++){

        for (int j = 0; j < N; j++) {
            if (flags[j] == 1) {	// 이전에 뽑힌 A팀과의 능력치 추가
                teamS1 += S[i][j] + S[j][i];	
            } 
            else{	// 전체 능력치의 합에서 A팀이 아닌 사람과의 능력치를 뺀다
                totalS -= S[i][j] + S[j][i];	
            }
        }
        
        flags[i] = 1;   // selected
        
        Pickup(num+1, i+1);

        flags[i] = 0;	// 이전 상태로 복귀

        teamS1 = curTeamS1;	
        totalS = curTotalS;
    }
}

 

 

 

소스 코드

#include <iostream>
using namespace std;

#define SIZE 20

int flags[SIZE];

int S[SIZE][SIZE];

int teamS1 = 0;
int totalS = 0;

int N;
int M;

int minV = 0x7fffffff;

void Pickup( int num, int start){

    if ( num == M){
   
        minV = min( minV, abs(totalS-teamS1));
        return;
    }

    int curTeamS1 = teamS1;
    int curTotalS = totalS;

    int to = N - M + num;
    for(int i = start; i < to; i++){

        for (int j = 0; j < N; j++) {
            if (flags[j] == 1) {
                teamS1 += S[i][j] + S[j][i];
            } 
            else{
                totalS -= S[i][j] + S[j][i];
            }
        }
        
        flags[i] = 1;   // selected
        
        Pickup(num+1, i+1);

        flags[i] = 0;

        teamS1 = curTeamS1;
        totalS = curTotalS;
    }
}

int main(){

    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    cin >> N;
    M = N / 2;	// 한 팀의 사람 수

    for( int i = 0; i < N; i++){
        for( int j = 0; j < N; j++){
            cin >> S[i][j];	// 사람들 간의 능력치
        }
    }

    for( int i = 0; i < N-1; i++){
        for( int j = i+1; j < N; j++){
            totalS += S[i][j] + S[j][i];	// 모든 사람들 간의 능력치 총합
        }
    }

    Pickup(0, 0);

    cout << minV;

    return 0;
}