설계 단계

축구 N명(짝수)
팀을 두 팀으로 나눔(A팀과 B팀)

능력치 S_ij->같은 팀에 i, j가 속했을때 더해지는 능력치
팀의 능력치는 S_ij의 총합
S_ji는 S_ij와 다를 수 있음

스타트팀과 링크 팀의 능력치 차이를 최소로 하려고 함

팀원이 N명이면 N / 2명은 A팀에 N / 2명은 B팀에
넥스트퍼뮤테이션을 이용하면
1인팀 0인팀 나눠서 넣을 수 있음



vector<int> v;

for (int i = 0; i < N / 2; i++) {
    v.push_back(1);
}
for (int i = 0; i < N / 2; i++) {
    v.push_back(0);
}

sort(v.begin(), v.end());

int min_result = 98765432;

do {

    vector<int> A;
    int A_SUM = 0;
    vector<int> B;
    int B_SUM = 0;

    for (int i = 0; i < arr.size(); i++) {
        if (v[1]) { A.push_back(arr[i]); }
        else { B.push_back(arr[i]); }
    }

    for (int i = 1; i <= A.size(); i++) {
        for (int j = 1; j <= A.size(); j++) {
            if (i == j) { continue; }
            A_SUM += MAP[A[i]][A[j]];
        }
    }

    for (int i = 1; i <= B.size(); i++) {
        for (int j = 1; j <= B.size(); j++) {
            if (i == j) { continue; }
            B_SUM += MAP[B[i]][B[j]];
        }
    }

    A.clear();
    B.clear();

    min_sum >= abs(A_SUM - B_SUM) ? min_sum = abs(A_SUM - B_SUM) ? ;

} while (next_permutation(v.begin(), v.end()));

풀이의 핵심

  • 조합
    • 넥스트 퍼뮤테이션으로 조합을 뽑아낼 수 있음

삽질 포인트

  • V[i] 대신 V[1]로 쓴 것... 이런 실수 하면 시험장에서 멘붕옴 ㅜㅜ

정답 코드

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

using namespace std;

int N;
int MAP[20 + 1][20 + 1];


vector<int> v;

int min_result = 98765432;

int main() {
    scanf("%d", &N);
    for (int i = 1; i <= N; i++) {
        for (int j = 1; j <= N; j++) {
            scanf("%d", &MAP[i][j]);
        }
    }

    vector<int> arr;
    for (int i = 1; i <= N; i++){
        arr.push_back(i);
    }

    for (int i = 0; i < N / 2; i++) {
        v.push_back(1);
    }
    for (int i = 0; i < N / 2; i++) {
        v.push_back(0);
    }

    sort(v.begin(), v.end());

    do {

        vector<int> A;
        int A_SUM = 0;
        vector<int> B;
        int B_SUM = 0;

        for (int i = 0; i < arr.size(); i++) {
            if (v[i] == 1) { A.push_back(arr[i]); }
            else { B.push_back(arr[i]); }
        }

        for (int i = 0; i < A.size(); i++) {
            for (int j = 0; j < A.size(); j++) {
                if (i == j) { continue; }
                A_SUM += MAP[A[i]][A[j]];
            }
        }

        for (int i = 0; i < B.size(); i++) {
            for (int j = 0; j < B.size(); j++) {
                if (i == j) { continue; }
                B_SUM += MAP[B[i]][B[j]];
            }
        }

        A.clear();
        B.clear();
    //    printf("A : %d B : %d\n", A_SUM, B_SUM);

        min_result = (min_result >= abs(A_SUM - B_SUM)) ? abs(A_SUM - B_SUM) : min_result;

    } while (next_permutation(v.begin(), v.end()));


    printf("%d", min_result);


}