BOJ 14889 스타트와 링크

1 개요

BOJ 14889 스타트와 링크

• 백준 온라인 저지 14889번 문제
• BOJ 22단계

2 C++

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

int N;
int MIN = 2000;
bool ok[20];
int S[20][20];

void solve(int idx, int cnt) {
    vector<int> start;
    vector<int> link;
    int S_start = 0;
    int S_link = 0;
    if(cnt == (N/2)) {
        for(int i=0; i<N; i++) {
            if(ok[i]) {
                start.push_back(i);
            } else {
                link.push_back(i);
            }
        }
        for(int i=0; i<(N/2); i++) {
            for(int j=0; j<(N/2); j++) {
                S_start += S[start[i]][start[j]];
                S_link += S[link[i]][link[j]];
            }
        }
        int diff = abs(S_start-S_link);
        if(diff < MIN) MIN = diff;
        return;
    }
    for(int i=idx; i<N; i++) {
        if(ok[i]) {
            continue;
        }
        ok[i] = true;
        solve(i, cnt+1);
        ok[i] = false;
    }
}

int main() {
    cin >> N;
    for(int i=0; i<N; i++) {
        for(int j=0; j<N; j++) {
            cin >> S[i][j];
        }
    }
    solve(0, 0);
    cout << MIN;
}