14889번: 스타트와 링크(백준 C++)

14889번: 스타트와 링크 링크

코드

#include <iostream>
#include <vector>
#include <climits>
using namespace std;

int arr[21][21];
bool check[21] = {0, };

vector <int> v(1, 1);

int min_num = INT_MAX;

int n;

void init(){
    for(int i=1; i<=n; i++){
        for(int j=1; j<=n; j++){
            cin >> arr[i][j];
        }
    }
}

void solve(int cnt, int x){
    if(cnt == (n/2 - 1)){
        vector <int> v2;
        int temp1 = 0;
        int temp2 = 0;
        int k = 2;
        for(int i=2; i<=n; i++){
            v2.push_back(i);
            for(int j=0; j<v.size(); j++){
                if(i == v[j]){
                    v2.pop_back();
                    continue;
                }
            }
        }
        for(int j=0; j<v.size(); j++){
            for(int k=(j+1); k<v.size(); k++){
                temp1 += arr[v[j]][v[k]];
                temp1 += arr[v[k]][v[j]];
                temp2 += arr[v2[j]][v2[k]];
                temp2 += arr[v2[k]][v2[j]];
            }
        }
        min_num = abs(temp1 - temp2) < min_num ? (abs(temp1 - temp2)) : min_num; 
    }
    else{
        for(int i=x; i<=n; i++){
            if(check[i] == 1) continue;
            check[i] = 1;
            v.push_back(i);
            solve(cnt+1, i+1);
            v.pop_back();
            check[i] = 0;
        }
    }    
}

int main() {
    cin >> n;
    init();
    solve(0, 2);
    cout << min_num;
    // your code goes here
    return 0;
}

풀이 및 사견

음... 뭔가 되게 복잡하게 풀었다는 느낌을 버릴수가없다.
그렇지만 일단 정답은 정답이니까..?

우선 이 문제 풀이에는 N과 M(2) 풀이 방법을 채용했다.

이게 무슨 뜻이냐면

위 그림의 경우에는 N이 4이다. 팀을 2:2로 나누어야 한다는 뜻이다.

그런데 잘 생각해보면 4개 중 2개를 고르면 나머지 2개는 자동으로 선택이된다.

딱히 팀을 나누는 것에 대한 구분은 없기때문에...

Team1 : Team2
[1, 2] : [3, 4] - CASE1

Team1 : Team2
[3, 4] : [1, 2] - CASE2

위 CASE1과 CASE2는 동일하다.

그렇기 때문에 N이 4라고 가정시, 찾아봐야 할 경우의 수는 3가지가 된다.

4C2 / 2 = 6 / 2 = 3

4명중 2명을 고르는 경우의 수.

1) 1 2 / 3 4
2) 1 3 / 2 4
3) 1 4 / 2 3
4) 2 3 / 1 4
5) 2 4 / 1 3
6) 3 4 / 1 2

여기서 1-6 / 2-5 / 3-4 는 동일하므로 다시 경우의 수를 반으로 나누면 3가지이다.

즉, 우리는 (1, 2) (1, 3), (1, 4) 만 찾으면 되는데

규칙이 있다. N이 계속 커져도 찾아야 하는 경우의 수에는 항상 1이 들어간다.

N이 6일때를 보자.

6C3 / 2 = 10 , 10가지인데

1) 1 2 3
2) 1 2 4
3) 1 2 5
4) 1 2 6
5) 1 3 4
6) 1 3 5
7) 1 3 6
8) 1 4 5
9) 1 4 6
10) 1 5 6

그렇다면 이를 통해 우리는 선택할 수 있다.
탐색소요시간을 줄이기 위해서 2 ~ N 까지의 수 중 N/2 - 1 개의 수를 선택하는 경우의 수를 찾고 그 경우의 수에 1을 추가해주면 된다.

이를 백트래킹으로 구현하면.

for(int i=x; i<=n; i++){
            if(check[i] == 1) continue;
            check[i] = 1;
            v.push_back(i);
            solve(cnt+1, i+1);
            v.pop_back();
            check[i] = 0;
   }

이렇게 나온다.

이 문제를 풀기 귀찮았던게 좀 이것저것 더할것도 많고 해서 그런건데

벡터 v에는 경우의 수중 하나의 경우가 들어있다. (예 - N이 4일때 v = [1, 2])
그럼 반대로 벡터v2에는 1~N중 벡터 v에 없는 수를 찾아서 넣어 경우를 생성한다.(v2 = [3, 4])

이후 문제 조건에 따라 능력치를 더해준 후 빼 본뒤 최소값을 구해주면 문제가 풀린다.