c++ 14889 스타트와 링크 (permutation)

 

 

스타트와 링크 

 

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

14889번: 스타트와 링크

 

 

 

구글에 14889 스타트와 링크를 검색했을 때 DFS, 백트래킹 풀이만 나오고 저와 비슷한 풀이는 발견하지 못하여서 prev_permutation을 활용한 풀이를 올립니다.

 

 

 

 

 

bool tmp 라는 배열을 이용해서 n/2 만큼 tmp[i] = 1을 해주어 절반을 1로 만들어 주었고

 

prev_permutation을 사용해 각각 스타트팀 , 링크 팀의 순서를 다르게 만들어 주었습니다.

 

점수를 계산한 방법은

 

tmp[i]=1 인 팀은 스타트팀, 아닌 팀은 링크팀으로 벡터에 저장을 해주었고

 

이중 for문을 통해 점수를 계산하여 각 팀의 최솟값을 정답으로 제출하였습니다.

 

#include <bits/stdc++.h>
using namespace std;

int n;

int arr[25][25];

bool tmp[25];

vector<int> ansArr;

int main(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    cin >> n;

    int ans = 999;

    for (int i = 0; i < n; i++)
    {
        for (int j = 0; j < n; j++)
        {
            cin >> arr[i][j];
        }
    }

    for (int i = 0; i < n / 2; i++)
    {
        tmp[i] = 1;
    }

    do
    {

        vector<int> stTeam;
        vector<int> liTeam;
        int st = 0;
        int link = 0;
        for (int i = 0; i < n; i++)
        {
            if (tmp[i] == 1)
            {
                stTeam.push_back(i);
            }
            else
            {
                liTeam.push_back(i);
            }
        }

        int stN = stTeam.size();
        int liN = liTeam.size();
        for (int i = 0; i < stN; i++)
        {
            for (int j = 0; j < stN; j++)
            {
                int num1 = stTeam[i];
                int num2 = stTeam[j];
                if (i == j)
                    continue;
                st += arr[num1][num2];
            }
        }

        for (int i = 0; i < liN; i++)
        {
            for (int j = 0; j < liN; j++)
            {
                int num1 = liTeam[i];
                int num2 = liTeam[j];
                if (i == j)
                    continue;
                link += arr[num1][num2];
            }
        }

        // cout << st << " " << link << "\n";

        ans = min(ans, abs(link - st));

    } while (prev_permutation(tmp, tmp + n));

    cout << ans;

    // 134 256

    //  13 14 31 34 41 43
}