[BOJ] 14889번 "스타트와 링크" (C++)

브루트포스 문제 연습해보려고 골랐다

브루트포스에 제일 자신없기 때문이다 . . .

 

그니까 짝수인 N개의 입력이 들어오면 N/2개의 조합끼리의 합이랑, 나머지의 합을 구하면 될것같다고 생각했다

 

그리고 문제 시간 제한이 2초나 되는데, N의 입력 제한이 20이길래, 조합의 중복까지 모두 구해도 될 것 같다고 생각해서 그냥 따로 중복에 관한 처리를 해주지 않고, 그냥 bool 배열 하나 만들어서 일반적으로 구했다 nPr을 구했나봐..

 

그랬더니 당연히 시간초과가 생겼다

겹치지 않는 조합으로 바꿔주니까 바로 해결되었다

0부터 n까지 차례대로 방문하며 돌기 때문에,

조합에서 다음 수를 구할땐 단순히 전의 수부터 끝 수까지 보면 된다

다음 수는 또 그 전 수부터 끝 수까지 중에 하나

이런 식으로 고쳤다

 

또, 방문을 했으면 visited 상태이기 때문에, visited배열의 값이 true인 것들과, false인 것들 따로따로 합을 구해줬고

(입력에서 대각선은 무조건 0이라고 했으니까 그냥 더해줌)

서로를 뺀 값의 절대값을, ascending order로 정렬해줄 수 있는 priority queue에 넣어줬다

그리고 priority queue의 맨 앞 값을 답으로 출력했다

#include<iostream>
#include<queue>
#include<algorithm>
#include<vector>
#include<functional>
using namespace std;

int n;
int info[20][20];
int goal;
bool visited[20];
priority_queue<int, vector<int>, greater<int>> ans;
vector<int> v;

void func(int turn,int now) {

    if (turn == goal) { // n/2개 탐색 끝나면

        v.clear();

        //고른 조합에 대한 합
        int sum = 0;
        for (int i = 0; i < n; i++) {
            if (visited[i]) {
                v.push_back(i);
            }
        }

        for (int i = 0; i < v.size(); i++) {
            for (int k = 0; k < v.size(); k++) {
                sum += info[v[i]][v[k]];
            }
        }

        v.clear();

        //고르지 않은 조합에 대한 합
        int remain = 0;

        for (int i = 0; i < n; i++) {
            if (!visited[i]) { //안고른 n/2개 선택해서 합 구하기
                v.push_back(i);
            }
        }

        for (int i = 0; i < goal; i++) {
            for (int k = 0; k < goal; k++) {
                remain += info[v[i]][v[k]];
            }
        }

        ans.push(abs(sum - remain));
        return;
    }

    for (int i = now; i < n; i++) {
        if (!visited[i]) {
            visited[i] = true;
            func(turn + 1,i);
            visited[i] = false;
        }
    }

}

int main() {
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);

    cin >> n;

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

    goal = n / 2;

    for (int i = 0; i < goal; i++) {
        visited[i] = true;
        func(1,i);
        visited[i] = false;
    }

    cout << ans.top();
}