백준 14889: 스타트와 링크

스타트팀과 링크팀의 점수를 계산하는 문제

다른 분들은 dfs를 사용해서 복잡도를 줄였던데 나는 무식하게 푸는 브루트포스를 공부중이라 0과1을 통한 조합을 이용해 풀었다. 시간복잡도는 어마무시하긴하지만 조건에 주어진 최대값이 해봐야 20이기 때문에 코드를 작성할만하다.

#include <iostream>
#include <algorithm>
#include <vector>
#include <limits.h>
using namespace std;
 
 
int main()
{
    int input;
    cin >> input;
    //능력치 입력받음
    vector<vector<int>> player (21);
    for (int i = 0; i < input; ++i)
    for (int j = 0; j < input; ++j)
    {
        int x;
        cin >> x;
        player[i].push_back(x);
    }
    vector<int> check;
    //0과 1을 순열을 돌려 사람을 선택
    for (int i = 0; i < input/2; ++i)
        check.push_back(0);
    for (int i = 0; i < input / 2; ++i)
        check.push_back(1);
    int min_val = INT_MAX;
    do
    {
        //0과 1의 순열을 통해 스타트팀과 링크팀을 구하고 해당 팀원의 능력치를 더해줌
        int start_team = 0;
        int link_team = 0;
        for (int i = 0; i < input; ++i)
        {
            if (check[i] == 0)
            {
                for (int j = 0;j < input; ++j)
                {
                    if (check[j] == 0)
                        start_team += player[i][j];
                }
            }
            if (check[i] == 1)
            {
                for (int j = 0; j < input; ++j)
                {
                    if (check[j] == 1)
                        link_team += player[i][j];
                }
            }
        }
        min_val = min(min_val, abs(start_team - link_team));
    } while (next_permutation(check.begin(), check.end()));
    //시간복잡도 O(nCn/2*n^2);
    cout << min_val << endl;
    return 0;
}