백트랙킹 - 백준 14899번 스타트와 링크

IDEA

보자마자 아 조합구현이네? 생각했다. 

1 ~ 8까지 있으면 조합을 통해 1,4,6,7 을 고르고 이걸 start라고 생각하면 선택받지못한 사람들은 link가 된다. 

start 내 사람들을 2명씩 골라서 점수를 내고, link도 똑같이 해 점수의 차를 비교하면 된다. 

 

•  n명 중 n/2명을 고르는 것도 조합으로 구현하고 n/2명 중 2명을 고르는 것도 조합으로 구현하려고 했는데 그러면 지저분해져서 어차피 2명이니까 투포인터로 합을 구했다.

• 선택 된 사람과 선택받지못한 사람을 어떻게 나누지? 에 대해 많이 고민했다. 

  temp라는 벡터에 넣어주고 1 ~ n 까지 temp안에 없으면 link 팀 있으면 start팀 이렇게 구성을 하다 보니까 

  시간이 더 걸릴 거 같더라,,,, 

  생각을 해보니 visited가 true인 i들은 모두 선택받은 즉 start가 될 i들이다.

  그래서 1 ~ n까지 방문처리가 됐다면start , 안됐다면 link팀으로 넣어 값을 계산해주었다.

결코 어렵지 않은 문제인데 너무 돌아돌아 풀었다. 

고민하는 시간이 오래걸리더라도 효율적으로 풀 수 있는 방법을 생각해보자.

 

CODE

#include <iostream>
#include <vector>
#include<algorithm>

using namespace std;

int ability[21][21];
int visited[21] = {false};
int n, min_ability = 100000000;

void check() {
    int start_score = 0, link_score = 0;
    vector<int>start; 
    vector<int>link;
    for (int i = 1; i <= n; i++) {
        if (visited[i]) start.push_back(i);
        else link.push_back(i);
    }


    for (int i = 0; i <n/2-1; i++) {
        for (int j = i + 1; j < n/2; j++) {
            start_score += (ability[start[i]][start[j]] + ability[start[j]][start[i]]);
            link_score += (ability[link[i]][link[j]] + ability[link[j]][link[i]]);
        }
    }
    min_ability = min(min_ability, abs(start_score - link_score));
}

void dfs(int start, int cnt) {
    if (cnt == n / 2) {
        check();
        return;
    }
    for (int i = start; i <= n; i++) { //combination으로 선택받으면 어차피 visited = true임 
        if (visited[i]) continue;
        visited[i] = true;
        dfs(i + 1, cnt + 1);
        visited[i] = false;
    }
}

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            scanf("%d", &ability[i][j]);
        }
    }
    dfs(1, 0);
    printf("%d", min_ability);
}