[BOJ 15661] 링크와 스타트

#문제

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

#풀이

이 문제의 경우, 백트래킹을 이용하여 팀을 나누고 그 중에서 2명을 뽑아내는 식으로 하였습니다.

해당 문제를 어디서 많이 보았다 했는데 예전에 풀었던 것과 거의 비슷했습니다.

혹시나 하여 링크를 달아드립니다.

[BOJ 스타트와 링크] : https://www.acmicpc.net/problem/14889

해당 문제와 거의 비슷하지만 한가지 조건이 추가가 되었습니다.

바로 전체 인원이 홀수일 수  있다는것!

해당 조건 때문에 뽑을때 고려해야 할 개수가 늘어났습니다... :(

전체 인원이 5명일때, 스타트팀이 2명 링크팀이 3명 또는 스타트팀이 3명 링크팀이 2명일 경우로 나누어지게 됩니다.

따라서 홀수일 때는 2명과 3명 모두 뽑아주어야 합니다.

백트래킹을 이용하여 전체 인원을 2개로 나누며, 이를 또 2명씩 뽑도록 하였습니다.

혹시 백트래킹을 모르신다면 구글링을 한번 하고 오시는것이 이해에 도움이 될꺼같습니다. :)

#코드

#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
 
//스탯정보
int stat[20][20];
//사람마다 팀 정보 -> 0 : 스타트팀 , 1 : 링크팀
int team[21];
int N;
int ans = 987654321;
 
//선택된 팀에 따라 2명씩 뽑기
int selectTwoPeople(int teamNum, int d, vector<int> man, int n){
    int result = 0;
    if(d == 2){
        //1,2를 뽑았을때 [1,2]와 [2,1]은 한번에 알 수 있다.
        //그렇기에 굳이 밑에서 1부터 돌리지 않아도 된다.
        return stat[man[0]-1][man[1]-1] + stat[man[1]-1][man[0]-1];
    }
    //어떤 팀에서 2명을 뽑기(백트래킹)
    for(int i = n; i <= N; i++){
        if(team[i] == teamNum){
            man.push_back(i);
            //해당 팀의 모든 스탯을 더해준다.
            result += selectTwoPeople(teamNum, d+1, man, i+1);
            man.pop_back();
        }
    }
    //다 더한 스탯을 넘겨준다.
    return result;
}
 
// isOdd = 1 홀수일때, isOdd = 0 짝수일때
void makeTeam(int num, int d, int isOdd){
    if(num == N/2 + isOdd){
        vector<int> teamStart;
        vector<int> teamLink;
        int statStart = selectTwoPeople(1, 0, teamStart, 1);
        int statLink = selectTwoPeople(0, 0, teamLink, 1);
        //팀간 스탯 차이를 최종 답과 비교. 더 작은 값을 넣는다.
        if(ans > abs(statStart - statLink)){
            ans = abs(statStart - statLink);
        }
    }
    //팀 뽑기(백트래킹)
    for(int i = d; i <= N; i++){
        if(team[i] == 1) continue;
        team[i] = 1;
        makeTeam(num+1, i+1, isOdd);
        team[i] = 0;
    }
}
 
int main(){
    cin >> N;
    for(int i = 0; i < N; i++){
        for(int j = 0; j < N; j++){
            cin >> stat[i][j];
        }
    }
    //홀수일때는 둘중 한팀은 한명이 더 많다.
    //따라서 양 팀다 한명씩 더 많은 경우의 수를 따져봐야한다.
    makeTeam(0,1,0);
    if(N%2 == 1){
        makeTeam(0,1,1);
    }
    cout << ans << endl;
    return 0;
}