[백준] 14889번 스타트와 링크

문제

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

풀이

시간을 너무 잡아먹은 문제였다. 초기 접근을 이상하게 해서 시간이 오래 걸린 점도 있었지만 재귀호출을 어려워하는 부분이 아직 있는 것 같다.

1. dfs와 백트래킹을 통해서 모든 경우를 돌아보는 완전탐색 문제다.
2. dfs로 스타트 팀으로 뽑을 선수 번호를 뽑는다
3. 스타트 팀으로 뽑은 선수가 N/2 명이 되면 두 팀의 능력치 차이를 구한다.
4. 위 과정을 반복한다.

스타트 팀으로만 뽑는 이유는 어차피 뽑지 않은 선수는 링크 팀이기 때문이다.
소스코드에 주석을 보면 이해하기가 쉽다.

소스코드

#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

#define MAX_SIZE 21

int n;
bool is_used[MAX_SIZE];
int s[MAX_SIZE][MAX_SIZE];
int ans = 987654321;

// curr_player번 선수를 스타트 팀으로 뽑는다, cnt : 뽑은 명수
void Dfs(int curr_player, int cnt)
{
    // n/2명을 뽑았으면 차이를 계산
    if (cnt == n / 2)
    {
        vector<int> team_link, team_start;

        // 뽑은 선수들은 스타트팀으로
        for (int i = 0; i < n; i++)
        {
            if (is_used[i]) team_start.push_back(i);
            else team_link.push_back(i);
        }

        // 스타트팀과 링크팀의 능력치 차이 구하기
        int stat_start = 0, stat_link = 0;
        for (int i = 0; i < team_start.size(); i++)
        {
            for (int j = i+1; j < team_start.size(); j++)
            {
                int start_x = team_start[i], start_y = team_start[j];
                int link_x = team_link[i], link_y = team_link[j];
                stat_start += s[start_x][start_y] + s[start_y][start_x];
                stat_link += s[link_x][link_y] + s[link_y][link_x];
            }
        }

        ans = min(ans, abs(stat_start - stat_link));
        return;
    }

    // 완전탐색
    for (int i = curr_player+1; i < n; i++)
    {
        if (is_used[i] == false)
        {
            is_used[i] = true;
            Dfs(i, cnt + 1);
            // 백트래킹
            is_used[i] = false;
        }
    }

}


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 >> s[i][j];
        }
    }

    Dfs(0,0);

    cout << ans << "\n";

    return 0;
}