[BOJ_C++] 14889번 : 스타트와 링크

code

 

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <cstring>
#include <stack>
#include <vector>
#include <cmath>
#include <string>

using namespace std;
int n, result = 10000000;
int nn[21][21];
bool check[21];

void dfs(int cnt, int pos) {
    if (cnt == n / 2) {
        int start, link;
        start = link = 0;

        for(int i=1; i<=n; i++)
            for (int j = 1; j <= n; j++) {
                if (i == j) continue;
                if (check[i] == true && check[j] == true)
                    start += nn[i][j];
                if (check[i] == false && check[j] == false)
                    link += nn[i][j];
            }

        result = min(result, abs(start - link));

        return;
    }

    for (int i = pos; i < n; i++) {
        check[i] = true;
        dfs(cnt + 1, i + 1);
        check[i] = false;
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    memset(nn, 0, sizeof(nn));
    cin >> n;

    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= n; j++)
            cin >> nn[i][j];

    dfs(0, 1);

    cout << result;

    return 0;
}

 

• 먼저 두 팀을 나누고 능력치 차가 최소가 되도록 한다.
• 팀을 나누는 방법으로는 dfs를 사용하여 가능한 모든 후보를 탐색하도록 한다.
• check[i]가 true인 dfs가 끝났다면 check[i]를 false로 바꿔 i가 스타트와 링크 팀에 있을 수 있는 모든 경우의 수를 계산하도록 한다.
• 두 팀의 능력치가 최소인 값을 출력하고 프로그램을 종료한다.

결과