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

14889번 스타트와 링크

문제 링크

스타트와 링크

분석

$N$명 있을 때, 두 팀으로 나누고 각 팀의 능력치 차이를 최소화 하는 문제입니다.

$N$은 항상 짝수입니다.
능력치는 $N \times N$ 크기의 2차원 배열입니다.

$S[i][j]$는 $i$번 사람과 $j$번 사람이 같은 팀일 때 발생하는 시너지 값입니다.

팀원 수는 $N/2$명씩 동일해야합니다.

두 팀의 능력치의 최소값을 찾아야합니다.

풀이

#include <iostream>
#include <vector>
#include <algorithm>
#include <cmath>
#include <climits>

using namespace std;

int minDiff = INT_MAX; // 최소 능력치 차이

// 능력치 계산 함수
int calculateDifference(const vector<vector<int>>& S, vector<bool>& selected, const int n)
{
    vector<int> teamA, teamB;

    // 선택 된 사람을 A팀, 선택 되지 않은 사람을 B팀
    for (int i = 0; i < n; i++)
    {
        if (selected[i])
        {
            teamA.push_back(i);
        }
        else
        {
            teamB.push_back(i);
        }
    }

    int sumA = 0, sumB = 0;

    // 각 팀의 능력치 합산
    for (int i = 0; i < n / 2; i++)
    {
        for (int j = 0; j < n / 2; j++)
        {
            if (i == j) continue;

            sumA += S[teamA[i]][teamA[j]];
            sumB += S[teamB[i]][teamB[j]];
        }
    }

    // 능력치 차이가 음수 일 수 있으므로, 절대값으로 변환
    return abs(sumA - sumB);
}

// 백트래킹 함수 (팀 구성)
void backtrack(const vector<vector<int>>& S, vector<bool>& selected, const int n, int idx, int count)
{
    // 팀원이 나눠진 경우
    if (count == n / 2)
    {
        // 능력치를 계산하고 능력치 차이가 최소값인지 확인 후 저장
        int calculateDiff = calculateDifference(S, selected, n);
        minDiff = min(minDiff, calculateDiff);
        return;
    }

    for (int i = idx; i < n; i++)
    {
        if (!selected[i])
        {
            selected[i] = true;  // i번 사람을 선택
            backtrack(S, selected, n, i + 1, count + 1);
            selected[i] = false; // 원상 복구
        }
    }
}

int main()
{
    int n;
    cin >> n;

    vector<vector<int>> S(n, vector<int>(n)); // n X n개의 배열
    vector<bool> selected(n); // 백트래킹을 위한 선택 배열

    // 능력치 입력 받기
    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> S[i][j];
        }
    }

    // 백트래킹 실행
    backtrack(S, selected, n, 0, 0);

    // 최소 차이 출력
    cout << minDiff << endl;
}

$N$명 중 $N/2$명을 선택하면 자동으로 나머지가 다른 팀이 됩니다.
따라서 백트래킹을 사용해 $N/2$명을 선택해 팀을 구성했습니다.

각 팀의 능력치는 $S[i][j] + S[j][i]$의 합으로 구합니다.

성능 요약

시간 복잡도는 $O(2^N \times N^2)$입니다.

• 백트래킹 탐색 경우의 수 $O(2^N)$입니다.
• 능력치 계산 $O(N^2)$
• $O(2^N \times N^2)$

공간 복잡도는 $O(N^2)$입니다.

• 능력치 배열 vector<vector<int>> S(n, vector<int>(n)) $O(N^2)$
• 선택 됐는지 저장하는 배열 vector<bool> selected(n) $O(N)$
• 재귀 호출 스택 $O(N)$
• $O(N^2 + N + N)$

메모리: 2024 KB

시간: 112 ms