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

언젠가 순열을 생성할 일이 있을 거 같아 기록해둠.

 

#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>
using namespace std;
int n;
int s[20][20];
int main()
{
    cin >> n;
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
            cin >> s[i][j];
    
    vector<int> v;
    v.resize(n);
    int answer=INT_MAX;
    for(int i=1; i<=n/2;i++)
    {
        int num_player_team_a = i;
        int num_player_team_b = n-i;

        //i: 어느 한팀의 인원 수
        for (int j = 0; j < num_player_team_a; j++)
            v[j] = 0;
		for (int j = num_player_team_a; j < n; j++) 
			v[j] = 1;

        do
        {
            vector<int> team_a; team_a.reserve(num_player_team_a);
            vector<int> team_b; team_b.reserve(num_player_team_b);
            
            for (int j = 0; j < n; j++)
            {
                if(v[j]==0) team_a.push_back(j);
                else team_b.push_back(j);        
            }

            int power_team_a=0;
            int power_team_b=0;

            for(int j = 0; j < num_player_team_a; j++)
                for(int k = 0; k < num_player_team_a; k++)
                {
                    power_team_a += s[team_a[j]][team_a[k]];
                }

            for(int j = 0; j < num_player_team_b; j++)
                for(int k = 0; k < num_player_team_b; k++)
                {
                    power_team_b += s[team_b[j]][team_b[k]];
                }

            answer = min(answer, abs(power_team_a-power_team_b));
        } while (next_permutation(v.begin(), v.end()));
    }
    cout << answer;
    return 0;
}