[백준 14889] 알고리즘 19일차 : 스타트와 링크

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

14889번: 스타트와 링크

백트래킹 C++

삼성 SW 역량 테스트 기출 문제 2

 

접근방법

팀선정에 N과 M(2)에서 사용했던 코드 재사용했다.(조합)

근데 보수관계의 조합은 필요없어서 첫번째로 들어오는 수가 0인 조합만 조사했다.

ischeck배열로 1이면 스타트팀, 0이면 링크팀에 넣고

또 스타트팀의 능력치 합산 점수, 링크팀의 능력치 합산 점수를 구한다.

그리고 이들의 차이는 gap변수(전역변수)에 저장하면서 최솟값을 갱신한다.

f함수 끝낸 후에 main에서 gap만 출력

 

<소스코드>

#include <iostream>
using namespace std;
static int N;
bool ischeck[20] = {false,};
int start[10];
int link[10];
int stats[20][20];
int gap = 10000;

void f(int cnt){
    if(cnt == N/2){
        int j = 0;
        for(int i = 0 ; i < N ; i++){
            if(!ischeck[i])
                link[j++] = i;
        }
        //팀선정 완료
        int sumOfStart = 0;
        int sumOfLink = 0;
        for(int i = 0 ; i < N/2 -1 ; i++){
            for(int j = i+1 ; j < N/2 ; j++){
                sumOfStart += (stats[start[i]][start[j]] + stats[start[j]][start[i]]);
                sumOfLink += (stats[link[i]][link[j]] + stats[link[j]][link[i]]);
            }
        }
        if(gap > abs(sumOfStart - sumOfLink))
            gap = abs(sumOfStart - sumOfLink);
        //한 조합에 대한 점수의 합 계산 완료
    }
    else{
        if(cnt == 0){
            if(!ischeck[0]){
                ischeck[0] = true;
                start[cnt] = 0;
                f(cnt+1);
                ischeck[0] = false;
            }
        }
        else{
            for(int i = start[cnt-1] ; i < N ; i++){
                if(!ischeck[i]){
                    ischeck[i] = true;
                    start[cnt] = i;
                    f(cnt+1);
                    ischeck[i] = false;
                }
            }
        }
    }
}

int main(){
    cin >> N;
    for(int i = 0 ; i < N ; i++){
        for(int j = 0 ; j < N ; j++)
            cin >> stats[i][j];
    }
    int cnt = 0;
    f(cnt);
    cout << gap;
    return 0;
}