[Algorithm]Baekjoon 15661번 :: 링크와 스타트

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

 

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_set>
 
using namespace std;
 
 
 
int n;
int ability[21][21] = { 0 };
vector<int> teams[2];
int answer = 0x3f3f3f3;
 
 
int GetSumAbility(int team)
{
    int sum = 0;
 
    for (int i = 0; i < teams[team].size() -1 ; ++i)
    {
        for (int j = i + 1; j < teams[team].size(); ++j)
        {
            int a = teams[team][i];
            int b = teams[team][j];
 
            sum += ability[a][b] + ability[b][a];
        }
    }
 
    return sum;
}
 
 
void DFS(int index)
{
    if (teams[0].size() + teams[1].size() == n)
    {
        if (teams[0].size() > 0 && teams[1].size() > 0)
        {
            answer = min(answer, abs(GetSumAbility(0) - GetSumAbility(1)));
        }
 
        return;
    }
 
    for (int i = 0; i < 2; ++i)
    {
        teams[i].push_back(index + 1);
        DFS(index + 1);
        teams[i].pop_back();
    }
}
 
 
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
 
    cin >> n;
 
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            cin >> ability[i][j];
        }
    }
 
    DFS(-1);
 
    cout << answer;
}
 
 

 

n명의 팀원이 주어지고 두 팀으로 나눴을 때 능력치의 총합차이가 최소가 되게해야하는 문제이다.

 

이 문제에서 포인트는 그냥 팀을 잘 나눠주기만 하면 된다. n과 m시리즈를 풀어봤으면 쉽게 풀어봤을, 모든 경우를 뽑아보는 문제이다.

그냥 매 차례마다 특정팀에 넣고 탐색진행 후, 다시 뺸다음 두번째팀에 넣고 탐색진행 후 다시 뺴기... 이런식으로 했다.

왜냐면 특정 플레이어는 동시에 두 팀에 소속되어있을 수 없으니, 다른팀에 넣기위해선 빼줘야 한다.

 

탐색을 진행하다 두 팀에 소속된 플레이어수가 n명만큼 되면 비교를 해줬다.