[백준][브루트포스] 14889 스타트와 링크 c++구현

목차

1. 문제
2. 문제 구현 방향
3. 참고
4. 코드 구현

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

문제

 

 

문제 구현 방향

N/2만큼을 고르는 모든 조합을 구한 뒤에 그 조합에서 2개를 고르는 조합을 통해 가장 작은 차이를 구해주었다.

 

 

참고

https://be-senior-developer.tistory.com/49

[알고리즘] 순열과 조합 c++ 구현

 

코드 구현

cpp

#include<iostream>
#include<algorithm>
#include<string.h>
#include<vector>
#include<map>
#include<queue>
#include<math.h>

using namespace std;

int N;

int board[100][100] = { 0 };
int minG = 9999999;
vector<int> v;
vector<int> v2;

//조합에서 2개씩 골라주어 더해준다.
int status(vector<int>&v) {
    int sum = 0;
    for (int i = 0; i < v.size(); i++) {
        for (int j = i + 1; j < v.size(); j++) {
            sum += board[v[i]][v[j]];
            sum += board[v[j]][v[i]];
        }
    }
    return sum;
}

//모든 조합을 구해준다.
void combi(int n, int here) {
    if (v.size() == n) {
        for (int j = 0; j < N; j++) {
            if (find(v.begin(), v.end(), j) == v.end()) {
                v2.push_back(j);
            }
        }
        minG = min(minG, abs(status(v) - status(v2)));
        v2.clear();
        return;
    }
    for (int i = here; i < N; i++) {
        v.push_back(i);
        combi(n, i + 1);
        v.pop_back();
    }

}


int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> N;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            cin >> board[i][j];
          
        }
    }
    combi(N/2, 0);

    cout << minG;
}