[백준,c++] 15661번 - 링크와 스타트

문제

15661번: 링크와 스타트

 

코드

#include <iostream>
using namespace std;

int map[21][21];
int N;
int min_ability = 1e9;
bool flag[21];

int score(){
    int start_score = 0;
    int link_score = 0;
    for(int i=1; i<=N; i++){
        for(int k=1; k<=N; k++){
            if(flag[i] && flag[k]){
                start_score += map[i][k];
            }
            if(!flag[i] && !flag[k]){
                link_score += map[i][k];
            }
        }
    }
    return abs(start_score - link_score);
}

void backtracking(int idx, int pick_cnt){
    
    if(pick_cnt >= 1 && pick_cnt <= N/2){
        min_ability = min(min_ability, score());
    }

    for(int i=idx; i<=N; i++){
        flag[i] = 1;
        backtracking(i + 1, pick_cnt + 1);
        flag[i] = 0;
    }
}
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    
    cin>>N;
    for(int i=1; i<=N; i++){
        for(int k=1; k<=N; k++){
            cin>>map[i][k];
        }
    }
    
    backtracking(1, 0);
    cout<<min_ability;
}

 

풀이

완전 탐색 문제입니다.

각각의 팀이 만들어지는 조합을 백트랙킹을 이용하여 생성하여 각각의 팀에 해당하는 스코어를 계산해서 차이의 최솟값을 찾아 출력하면 됩니다.

각각의 팀이 만들어지는 과정을 잘 살펴보면 최대 총인원(N) / 2 의 개수만 선택하면 팀을 나눌 수 있습니다. 예를 들면 다음과 같습니다.

A, B, C, D, E의 인원이 있을 경우

1. {A, {B, C, D, E}}, {B, {A, C, D, E}}.... {E, {A, B, C, D}}의 경우처럼 하나를 고르고 나머지를 전부 같은 팀으로 판정하면 경우의 수가 만들어집니다.
2. {{A, B}, {C, D, E}}, {{A, C}, {B, D, E}}, {{A, D, {B, C, E}}... 와 같이 두 개를 고르고 나머지를 전부 같은 팀으로 판정하면 경우의 수가 만들어집니다.
3. {{A, B, C}, {D, E}}... 같이 세 개를 고르는 경우 바로 위에서 두개를 고른 경우와 경우의 수가 같기 때문에 굳이 중복해서 판별하지 않아도 됩니다.

따라서  최대 총인원(N) / 2 의 개수만 선택하면 팀이 나누어지는 모든 경우의 수를 따져볼 수 있습니다.