문제 푼 날짜 : 2021-09-18

문제

문제 링크 : https://www.acmicpc.net/problem/14889

접근 및 풀이

간단한 백트래킹 문제였다.
스타트팀과 링크팀으로 반반을 나눠주면 되기 때문에 조합을 구현하였다.
각 팀에 선택된 사람들에 해당하는 능력치 값들을 다 더해주고, 그 차이값을 업데이트 해주었다.

코드

// 백준 14889번 : 스타트와 링크
#include <iostream>
#include <algorithm>
#include <vector>

using namespace std;

int N;
int arr[21][21];
bool visited[21] = { false, };
int diff = 987654321;

void dfs(int cnt, int num) {
    if (cnt == N/2) {
        vector<int> start, link;
        int sScore = 0, lScore = 0;
        for (int i = 1; i <= N; i++) {
            if (visited[i]) {
                start.push_back(i);
            } else {
                link.push_back(i);
            }
        }

        for (int i = 0; i < N/2; i++) {
            for (int j = 0; j < N/2; j++) {
                sScore += arr[start[i] - 1][start[j] - 1];
                lScore += arr[link[i] - 1][link[j] - 1];
            }
        }
        diff = min(diff, abs(sScore - lScore));
        return;
    }

    for (int i = num; i <= N; i++) {
        if (visited[i]) {
            continue;
        }
        visited[i] = true;
        dfs(cnt + 1, i);
        visited[i] = false;
    }
}

int main() {
    cin >> N;

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> arr[i][j];
        }
    }
    dfs(0, 1);

    cout << diff;
    return 0;
}

결과

피드백

좀 더 침착하게 차근차근히 생각하는 연습을 하자.