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

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

14889번: 스타트와 링크

풀이) 

selected 배열을 만들어서 N명의 선수가 selected배열에 들어간 경우와 안들어간 경우를 나누어서 조합을 구성했다. 이후 선택된 선수의 합이 N / 2가 되었을 때 selected배열을 통해 선택된 선수를 스타트팀에, 선택되지 않은 선수를 link팀에 넣어서 팀을 나누어 구성하였고, 2중포문을 통해 start팀의 합과 link팀의 합을 구하였다. 이후 두 값의 차를 구하면 된다.

 

※ 26번째 줄에서 i < N 대신 i < N - 1을 넣으면 팀의 중복 계산되는 부분이 빠지기 때문에 더 효율적인 알고리즘이 된다. 

#include <iostream>
using namespace std;

int N, result = 2e9;
int map[21][21], selected[21], team_start[11], team_link[11];

void dfs(int position, int cnt) {
    if (cnt == N / 2) {
        int team_start_idx = 0, team_start_sum = 0, team_link_idx = 0, team_link_sum = 0;
        for (int i = 0; i < N; i++) {
            if (selected[i])
                team_start[team_start_idx++] = i;
            else
                team_link[team_link_idx++] = i;
        }
        for (int i = 0; i < N / 2; i++) {
            for (int j = i + 1; j < N / 2; j++) {
                team_start_sum += map[team_start[i]][team_start[j]] + map[team_start[j]][team_start[i]];
                team_link_sum += map[team_link[i]][team_link[j]] + map[team_link[j]][team_link[i]];
            }
        }
        result = min(result, abs(team_start_sum - team_link_sum));
        for(int i = 0; i < N / 2; i++)
            team_start[i] = team_link[i] = 0;
    }
    for (int i = position; i < N; i++) {
        if (!selected[i]) {
            selected[i] = 1;
            dfs(i, cnt + 1);
            selected[i] = 0;
        }
    }
}
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 >> map[i][j];
    dfs(0, 0);
    cout << result;
    return (0);
}

 

 

제 코드는 절대 완벽하지 않습니다

더 좋은 풀이방법 혹은 코드에 관한 질문이 있으시면 언제든 댓글주세요!