[BOJ/C++] 스타트와 링크(14889번)

1. 개요

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

14889번: 스타트와 링크

1-1. 설명

오늘은 스사트링크에 다니는 사람들이 모여 축구를 한다. 축구를 위해 모인사람은 N명이며, 이는 짝수이다. 이제 N/2명으로 이루어진 스타트팀과 링크팀으로 사람을 나눠야한다. 우리는 능력치를 조사하여 각 팀에 더해지는 능력치가 최소일때를 찾는 프로그램을 구현한다. 문제의 자세한 설명은 위의 링크를 참고한다. 

1-2. 제한 사항

 - 첫 줄에 N이 주어지며, N은 4 이상 20 이하 짝수

 - 둘째 줄부터 N개의 줄에 표가 주어지며 이 표의 수는 100보다 작거나 같은 정수

---

2. 구현

2-1. 풀이

문제를 이해하기까지 시간이 조금 오래걸렸다. 문제를 확실하게 이해하고나면 조합을 사용하여 푸는 것을 알게 될 것이며, DFS(재귀)를 통해 문제를 풀어나갔다. 일정 깊이가 되면 능력치의 차이를 구하게끔 하였다. 

2-2. 코드

#include <iostream>
#include <cmath>
using namespace std;

int nums[20][20];
bool visited[20];
int N, start = 0, link = 0, minNum = 100;

void DFS(int i, int j);
void calculate();

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

    cin >> N;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) cin >> nums[i][j];
    }
    
    DFS(0, 0);

    cout << minNum;
    return 0;
}

void DFS(int depth, int index) {
    if (depth == N / 2) { 
        // 한 팀에 속한 인원 수 N/2로 채워지면 능력치를 구함
        // 왜 N/2? 한쪽이 꾸려지면 자동으로 다른쪽도 꾸려지기 때문
        calculate();
    }
    else {
        for (int i = index; i < N; i++) {
            if (!visited[i]) {
                visited[i] = true;
                DFS(depth + 1, i + 1);
                visited[i] = false;
            }
        }
    }
}

void calculate() {
    // 방문한 팀은 스타트, 안한 팀은 링크 -> 능력치 구할 수 있음
    // 능력치 차이의 절댓값과 현재 저장된 차이의 최솟값을 비교하며 갱신
    start = 0, link = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            if (visited[i] && visited[j]) start += nums[i][j];
            else if (!visited[i] && !visited[j]) link += nums[i][j];
        }
    }
    minNum = min(abs(start - link), minNum);
}