14889. 스타트와 링크

사람은 총 N명, 최대 20명

이를 순열로 늘어 놓아서 앞에는 스타트팀, 뒤에는 링크팀으로 하면 중복계산도 상당히 많고,

총 경우의 수는 20! = 상당히 큰 수이다 >>>>>>>>>>>> 1억

당연히 시간초과가 난다.

 

문제를 풀면서 자연스럽게 생각할 수 있는 것은 사실 조합이다.

₂₀C₁₀ 는 10! 보다 작을 것이라는 것을 예측할 수 있는데 실제로 그 결과는 10!(3백만)보다 훨씬 작다. 18만정도이다.

여기에 각 팀 스코어를 계산해야하는 시간이 (N/2) x (N/2) 이므로 100이라고 하면, 1800만 < 2초 안에 가능하다.

 

내가 맨 처음에 한 것은, 

예를들어 1, 2, 3을 뽑았으면 총 1, 2, 3, 4, 5, 6 인 set에서 1, 2, 3을 뽑는 것이다.

즉 4, 5, 6을 만드는 것. 근데 이것하는데 NlogN 시간이 걸리다 보니 확실히 시간이 더 많이 걸리긴 하더라.

코드도 뭔가 지저분하고 말이다. 

#include <cstdio>
#include <set>
using std::set;
int n;
int s[20][20];
int a[20], b[20];
int min_ans = 0x7fffffff;

void dfs(int depth, int start){
    if (depth == n/2){
        set<int> team2;
        for (int i=0; i<n; ++i) team2.insert(i);
        for (int i=0; i<n/2; ++i) {
            auto iter = team2.find(a[i]);
            team2.erase(iter);
        }
        int idx = 0;
        for (auto iter = team2.begin(); iter != team2.end(); ++iter){
            b[idx++] = *iter;
        }

        int score1 = 0, score2 = 0;
        for (int i=0; i<n/2; ++i){
            for (int j=0; j<n/2; ++j){
                score1 += s[a[i]][a[j]];
                score2 += s[b[i]][b[j]];
            }
        }
        int dif = score1 - score2;
        if (dif < 0) dif = -dif;
        if (min_ans > dif) min_ans = dif;
        return;
    }
    for (int i=start; i<n; ++i){
        a[depth] = i;
        dfs(depth + 1, i + 1);
    }
}


int main() {
    scanf("%d", &n);
    for (int i=0; i<n; ++i){
        for (int j=0; j<n; ++j){
            scanf("%d", &s[i][j]);
        }
    }
    dfs(0, 0);
    printf("%d\n", min_ans);
    return 0;
}

 

두 번째 푼것은 정석이다.

이렇게들 많이 푼다.

인덱스를 저장하는 게 아이디어 정말 좋은 것 같다.

이 것은 팀 나누는 데  O(N) 밖에 안걸리므로, 시간이 조금 더 줄어든다.

#include <cstdio>
int n;
int s[20][20];
int team1[10], team2[10];
bool idx[20];
int min_ans = 0x7fffffff;

void calculate(){
    int size1 = 0, size2 = 0;
    for (int i=0; i<n; ++i){
        if (idx[i]) team1[size1++] = i;
        else team2[size2++] = i; 
    }

    int score1 = 0, score2 = 0;
    for (int i=0; i<n/2; ++i){
        for (int j=i+1; j<n/2; ++j){
            score1 += s[team1[i]][team1[j]] + s[team1[j]][team1[i]];
            score2 += s[team2[i]][team2[j]] + s[team2[j]][team2[i]];
        }
    }
    int dif = score1 - score2;
    if (dif < 0) dif = -dif;
    if (min_ans > dif) min_ans = dif;
}

void dfs(int depth, int start){
    if (depth == (n / 2)){
        calculate();
        return;
    }
    for (int i=start; i<n; ++i){
        idx[i] = true;
        dfs(depth + 1, i + 1);
        idx[i] = false;
    }
}


int main() {
    scanf("%d", &n);
    for (int i=0; i<n; ++i){
        for (int j=0; j<n; ++j){
            scanf("%d", &s[i][j]);
        }
    }
    dfs(0, 0);
    printf("%d\n", min_ans);
    return 0;
}

 

마지막으로는, dfs를 두번으로 쪼개서, 아예 팀을 나누면서 탐색하는 방법이다.

이 방법은 획기적이다.. 이렇게 되면 기저조건에서 팀을 나누지 않아도 되므로 N 시간이 사라져서 시간이 조금 더 감소한다.

아, 물론 이 세가지 방법 다 최악 시간복잡도를 따져봤을 때는 O(N^2 NC(N/2))로 같다.

N^2 + NlogN 인지

N^2 + N 인지 정도 다를 뿐인 것 같다.

#include <cstdio>
int n;
int s[20][20];
int t1[10], t2[10];
int idx1, idx2;
int minans = 0x7fffffff;

void dfs(int dep, int cur){
    if (dep == n){
        int score1 = 0, score2 = 0;
        for (int i=0; i<n/2; ++i){
            for (int j=i+1; j<n/2; ++j){
                score1 += s[t1[i]][t1[j]] + s[t1[j]][t1[i]];
                score2 += s[t2[i]][t2[j]] + s[t2[j]][t2[i]];
            }
        }
        int dif = score1 - score2;
        if (dif < 0) dif = -dif;
        if (minans > dif) minans = dif;
        return;
    }

    if (idx1 < n/2){
        t1[idx1++] = cur;
        dfs(dep + 1, cur + 1);
        --idx1;
    }

    if (idx2 < n/2){
        t2[idx2++] = cur;
        dfs(dep + 1, cur + 1);
        --idx2;
    }
}

int main() {
    scanf("%d", &n);
    for (int i=0; i<n; ++i){
        for (int j=0; j<n; ++j){
            scanf("%d", &s[i][j]);
        }
    }
    dfs(0, 0);
    printf("%d\n", minans);
    return 0;
}

 

다음에는 그냥 무난하게 가운데 같은 방법 쓰겠다.

일단 머리가 기억하고 있어야 하니까. 정석이 좋은 법이다.