[ 백준 15661] 링크와 스타트 (C++)

백준의 링크와스타트(15661) 문제이다.

( 문제 바로가기 )

[ 문제설명 ]

- 전체 사람의 수와, 사람과 사람이 만났을 때의 시너지가 맵으로 주어진다. 그런데 순서가 바뀌면 시너지가 다르다.

  즉, A와B가 팀이 됬을 때의 시너지와 B와A가 팀이 되었을 때의 시너지가 다르다.

  팀 전체의 시너지는 Sab + Sba로 나타낸다.

- 이렇게 전체 사람의 수를 2팀으로 나누었을 때, 팀 전체의 시너지의 차이가 가장 적게 날 때 , 그 차이를 출력하는 것이

  문제이다.

[ 문제풀이 ]

1. 이 문제는 가능한 나올 수 있는 모든 팀의 조합을 다 만들어보고 팀의 시너지를 계산해서 최소값을 구하면 된다.

2. 여기서, 조합 개념이 사용된다. 얼핏보면, A와B가 팀이 되었을 때와, B와 A가 팀이 되었을 때의 시너지가 다르기 때문에

   순열인것 처럼 생각할 수 있지만, 결과적으로 본다면 A와B가 팀이되든 B와A가 팀이되든 결국 팀의 시너지는

   Sab + Sba 로 똑같기 때문에 조합의 개념이다.

3. 조합을 통해서(조합에 대한 자세한 설명은 BFS/DFS의 로또 문제 풀이를 참고하기 바란다) 팀을 2개로 나눈다.

   [ 로또 문제풀이 바로가기 ]

   사실 팀을 2개로 나눌 필요도 없이, 조합을 구현하면서 선택한 사람의 수가 N/2명이 되면,

    선택당한 사람과 선택받지 못한 사람 이렇게 2개의 팀으로 나뉘기 때문에 조합만 구해주면 된다.

4. 팀을 나눴다면 팀의 시너지를 구하면 된다. 나는 이부분에서 Vector를 사용하였다.

   선택당한 사람에 대해서는 Link_Team을 관리하는 Vector에, 반대인 사람에 대해서는 Star_Team을 관리하는 Vector에

   넣어주고, MAP을 이용해서 시너지를 계산하였다.

   계산할 때마다, 최소값을 갱신해 주었다.

[ 소스코드 ]

#include<iostream>
#include<vector>
#include<cmath>
 
#define endl "\n"
#define MAX 20
using namespace std;
 
int N, Answer = 999999;
int MAP[MAX][MAX];
bool Select[MAX];
 
int Min(int A, int B) { if (A < B) return A; return B; }
 
void Input()
{
    cin >> N;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            cin >> MAP[i][j];
        }
    }
}
 
int Calculate_Synergy(vector<int> V)
{
    int Sum = 0;
    for (int i = 0; i < V.size(); i++)
    {
        for (int j = 0; j < V.size(); j++)
        {
            if (i == j) continue;
            Sum = Sum + MAP[V.at(i)][V.at(j)];
        }
    }
    return Sum;
}
 
void Calculate()
{
    vector<int> Link, Start;
 
    for (int i = 0; i < N; i++)
    {
        if (Select[i] == true) Link.push_back(i);
        else Start.push_back(i);
    }
 
    int Synergy_Link = Calculate_Synergy(Link);
    int Synergy_Start = Calculate_Synergy(Start);
    int Diff = abs(Synergy_Link - Synergy_Start);
 
    Answer = Min(Answer, Diff);
}
 
void Divide_Team(int Index, int Cnt)
{
    if (Cnt == N / 2)
    {
        Calculate();
        return;
    }
 
    for (int i = Index; i < N; i++)
    {
        if (Select[i] == true) continue;
        Select[i] = true;
        Divide_Team(i, Cnt + 1);
        Select[i] = false;
    }
}
 
void Solution()
{
    Divide_Team(0, 0);
    cout << Answer << endl;
}
 
void Solve()
{
    Input();
    Solution();
}
 
int main(void)
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    //freopen("Input.txt", "r", stdin);
    Solve();
 
    return 0;
}