[백준] 14889 스타트와 링크

14889번: 스타트와 링크

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int s[20][20];
int n;
int go(int index, vector<int> &first, vector<int> &second) {
    if (index == n) {
        if (first.size() != n/2) return -1;
        if (second.size() != n/2) return -1;
        int t1 = 0;
        int t2 = 0;
        for (int i=0; i<n/2; i++) {
            for (int j=0; j<n/2; j++) {
                if (i == j) continue;
                t1 += s[first[i]][first[j]];
                t2 += s[second[i]][second[j]];
            }
        }
        int diff = t1-t2;
        if (diff < 0) diff = -diff;
        return diff;
    }
    int ans = -1;
    first.push_back(index);
    int t1 = go(index+1, first, second);
    if (ans == -1 || (t1 != -1 && ans > t1)) {
        ans = t1;
    }
    first.pop_back();
    second.push_back(index);
    int t2 = go(index+1, first, second);
    if (ans == -1 || (t2 != -1 && ans > t2)) {
        ans = t2;
    }
    second.pop_back();
    return ans;
}
int main() {
    cin >> n;
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            cin >> s[i][j];
        }
    }
    vector<int> first, second;
    cout << go(0, first, second) << '\n';
} 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int s[20][20];
int n;
int go(int index, vector<int> &first, vector<int> &second) {
    if (index == n) {
        if (first.size() != n/2) return -1;
        if (second.size() != n/2) return -1;
        int t1 = 0;
        int t2 = 0;
        for (int i=0; i<n/2; i++) {
            for (int j=0; j<n/2; j++) {
                if (i == j) continue;
                t1 += s[first[i]][first[j]];
                t2 += s[second[i]][second[j]];
            }
        }
        int diff = t1-t2;
        if (diff < 0) diff = -diff;
        return diff;
    }
    if (first.size() > n/2) return -1;
    if (second.size() > n/2) return -1;
    int ans = -1;
    first.push_back(index);
    int t1 = go(index+1, first, second);
    if (ans == -1 || (t1 != -1 && ans > t1)) {
        ans = t1;
    }
    first.pop_back();
    second.push_back(index);
    int t2 = go(index+1, first, second);
    if (ans == -1 || (t2 != -1 && ans > t2)) {
        ans = t2;
    }
    second.pop_back();
    return ans;
}
int main() {
    cin >> n;
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            cin >> s[i][j];
        }
    }
    vector<int> first, second;
    cout << go(0, first, second) << '\n';
} 

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int s[20][20];
int main() {
    int n;
    cin >> n;
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            cin >> s[i][j];
        }
    }
    int ans = -1;
    for (int i=0; i<(1<<n); i++) {
        vector<int> first, second;
        for (int j=0; j<n; j++) {
            if (i&(1<<j)) {
                first.push_back(j);
            } else {
                second.push_back(j);
            }
        }
        if (first.size() != n/2) continue;
        int t1 = 0;
        int t2 = 0;
        for (int l1=0; l1<n/2; l1++) {
            for (int l2=0; l2<n/2; l2++) {
                if (l1 == l2) continue;
                t1 += s[first[l1]][first[l2]];
                t2 += s[second[l1]][second[l2]];
            }
        }
        int diff = t1-t2;
        if (diff < 0) diff = -diff;
        if (ans == -1 || ans > diff) {
            ans = diff;
        }
    }
    cout << ans << '\n';
} 

 

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
int s[20][20];
int main() {
    int n;
    cin >> n;
    for (int i=0; i<n; i++) {
        for (int j=0; j<n; j++) {
            cin >> s[i][j];
        }
    }
    int ans = -1;
    for (int i=0; i<(1<<n); i++) {
        int cnt = 0;
        for (int j=0; j<n; j++) {
            if (i&(1<<j)) cnt += 1;
        }
        if (cnt != n/2) continue;
        vector<int> first, second;
        for (int j=0; j<n; j++) {
            if (i&(1<<j)) {
                first.push_back(j);
            } else {
                second.push_back(j);
            }
        }
        int t1 = 0;
        int t2 = 0;
        for (int l1=0; l1<n/2; l1++) {
            for (int l2=0; l2<n/2; l2++) {
                if (l1 == l2) continue;
                t1 += s[first[l1]][first[l2]];
                t2 += s[second[l1]][second[l2]];
            }
        }
        int diff = t1-t2;
        if (diff < 0) diff = -diff;
        if (ans == -1 || ans > diff) {
            ans = diff;
        }
    }
    cout << ans << '\n';
}