백준 14889 (스타트와 링크) / C++

문제 링크 : https://www.acmicpc.net/problem/14889

14889번: 스타트와 링크

> 풀이

 

N이 20보다 작거나 같으므로 시간제한에 구애받지않고 완전탐색(브루트포스)이 가능합니다.

 

스타트와 링크로 잘 나누기만 하면 되는데, 저는 처음에 00001111 식으로 절반으로 나눠 수열을 만들고, next_permutation으로 반복문을 돌았습니다.

 

최솟값을 구할 때 <climits(limits.h)> 헤더를 추가하면 자료형의 최댓값을 쉽게 가져올 수 있습니다.

#include <cstdio>
#include <cstdlib>
#include <climits>
#include <algorithm>
#include <vector>
using namespace std;

int main() {
        int N;
        int S[20][20];
        int _min = INT_MAX;
        int start_sum, link_sum;
        vector<int> v;

        scanf("%d", &N);
        for (int i = 0; i < N; i++) 
                for(int j = 0; j < N; j++)
                        scanf("%d", &S[i][j]);
                        
        for (int i = 0; i < N/2; i++) v.push_back(0);
        for (int i = 0; i < N/2; i++) v.push_back(1);

        do {
                start_sum = 0, link_sum = 0;
                vector<int> start, link;
                for (int i = 0; i < N; i++) {
                        if (v[i] == 0) start.push_back(i);
                        else link.push_back(i);
                }

                for (int i = 0; i < N/2; i++) {
                        for (int j = i + 1; j < N/2; j++) {
                                if (i == j) continue;
                                start_sum += S[start[i]][start[j]] + S[start[j]][start[i]];
                                link_sum += S[link[i]][link[j]] + S[link[j]][link[i]];
                        }                       
                }
                _min = min(_min, abs(start_sum - link_sum));

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

        printf("%d", _min);
        return 0;
}

(개발 환경 : vs code)