[Algorithm]백준 - 스타트와 링크

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

알고리즘 설명은 주소 참고

N이 작기 때문에 Brute force 방법을 이용해 풀기로 했고 모든 팀 조합을 조사해서 min 값을 출력하면 된다고 생각했다.

이 문제의 핵심은 조합 (Combination)을 짧은 시간 내에 구할 수 있느냐다.

순열과 조합에 대한 개념은 아래 글을 참고해주길 바란다.

(글 작성중)

코드는 아래와 같다.

    #include<iostream>
    #include<vector>
    #include<algorithm>
 
    using namespace std;
 
    vector<vector<int> > matrix;
    vector<int> member;
    int minDiffer = 0xfffff;
    int combs[20][20] = {};
    void getDiffer(int n)
    {
        vector<int> startT;
        vector<int> linkT;
        int startScore = 0;
        int linkScore = 0;
        for (int i = 0; i < n; i++)
        {
            if (member[i] == 1)
            {
                startT.push_back(i);
            }
            else
            {
                linkT.push_back(i);
            }
        }
        for (int i = 0; i < n / 2; i++)
        {
            for (int j = i + 1; j < n / 2; j++)
            {
                startScore += matrix[startT[i]][startT[j]] + matrix[startT[j]][startT[i]];
            }
        }
        for (int i = 0; i < n / 2; i++)
        {
            for (int j = i + 1; j < n / 2; j++)
            {
                linkScore += matrix[linkT[i]][linkT[j]] + matrix[linkT[j]][linkT[i]];
            }
        }
        int difference = abs(startScore - linkScore);
        if (minDiffer > difference)
        {
            minDiffer = difference;
        }
        return;
    }
    int getCombination(int n, int r)
    {
        if (n == r)
            return 1;
        if (r == 1)
            return n;
        if (combs[n][r] > 0)
        {
            return combs[n][r];
        }
        else
        {
            return combs[n][r] = getCombination(n - 1, r) + getCombination(n - 1, r - 1);
        }
    }
    void calculate(int n)
    {
        member.resize(n);
        for (int i = 0; i < n; i++)
        {
            if (i < n / 2)
                member[i] = 0;
            else
                member[i] = 1;
        }
        do
        {
            getDiffer(n);
        } while (next_permutation(member.begin(), member.end() ) );
 
    }
 
    int main(int argc, char** args)
    {
        int N;
        cin >> N;
        matrix.resize(N);
        member.resize(N);
        for (int i = 0; i < N; i++)
        {
            matrix[i].resize(N);
        }
        for (int i = 0; i < N; i++)
        {
            for (int j = 0; j < N; j++)
            {
                cin >> matrix[i][j];
            }
        }
        calculate(N);
        cout << minDiffer << endl;
 
        return 0;
    }

풀이 시간 : 3 ~ 4시간

풀이 중 문제점 :

 1. Combination을 구하는 효율적인 방법을 몰라 혼자 해결하려다가 헤메었다. 결국 웹 검색을 통해 next_permutation 사용법을 알아보고 해결.

 2. nCr을 재귀 계산으로 구해서 brute force 방법을 적용하려다가 시간 초과가 남, next_permutation의 리턴값을 활용해 해결