백준 14889 스타트와 링크

조합을 이용한 문제이다.
그리 어렵지 않았으나 더 간단한 풀이가 존재했다.

내 아이디어

1. 우선 처음에 조합과 next_permutation을 이용해서 팀을 두개로 나눈다. 0부터 N-1까지의 수를 부여한다.
2. 나눈 각자의 팀내에서 백트래킹을 사용해서 경우의 수를 조사한다.
3. 모든 경우의 수를 도출해낸 뒤 최소값을 출력한다.

내 코드

/*
- 조합, 백트래킹 사용
*/

#include <bits/stdc++.h>
using namespace std;

int n; // 짝수
int board[22][22];
int mn = 0x7f7f7f7f; 
int start_sum = 0;
int link_sum = 0;
int start[11], link[11];
bool start_vis[11], link_vis[11];
int s_arr[2], l_arr[2];

void start_func(int k) {
    if(k == 2) {
        start_sum += board[s_arr[0]][s_arr[1]];
        return;
    }
    for(int i = 0; i < n/2; i++) {
        if(start_vis[i]) continue;
        s_arr[k] = start[i];
        start_vis[i] = 1;
        start_func(k+1);
        start_vis[i] = 0;
    }
}

void link_func(int k) {
    if(k == 2) {
        link_sum += board[l_arr[0]][l_arr[1]];
        return;
    }
    for(int i = 0; i < n/2; i++) {
        if(link_vis[i]) continue;
        l_arr[k] = link[i];
        link_vis[i] = 1;
        link_func(k+1);
        link_vis[i] = 0;
    }
}

int main(void) {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for(int i = 0; i < n; i++) {
        for(int j = 0; j < n; j++) {
            cin >> board[i][j];
        }
    }
    vector<int>brute (n, 1);
    fill(brute.begin(), brute.end()-(n/2), 0);
    do {
        // 팀 선택
        for(int i = 0, s_idx = 0, l_idx = 0; i < n; i++) {
            if(brute[i] == 0) start[s_idx++] = i;
            if(brute[i] == 1) link[l_idx++] = i;
        }
        start_sum = 0; link_sum = 0; fill(start_vis, start_vis+11, 0); fill(link_vis, link_vis+11, 0);
        start_func(0); link_func(0);
        mn = min(mn, abs(start_sum-link_sum));
    } while(next_permutation(brute.begin(), brute.end()));
    cout << mn;
}

더 좋은 아이디어

1. 똑같이 조합과 next_permutation을 이용해서 팀을 두개로 나눈다.
여기서 굳이 나는 나눈 팀의 vector를 만들고 1부터 N까지의 수를 부여하려 했다. 하지 않아도 되는 부분이었다. 수를 부여하지 않고 vector 내의 index를 사용해도 충분했다.
2. 여기서 백트래킹을 사용하지 않고, 어차피 팀은 구분되어 있으니 
조건문을 통해 같은 팀은 피하면서, 변수에 각 값을 더하는 식으로 한다.

코드

#include <bits/stdc++.h>
using namespace std;

int n, board[22][22];
int mn = 0x7f7f7f7f;

int main(void) {
   ios::sync_with_stdio(0);
   cin.tie(0);
   cin >> n;
   for(int i = 0; i < n; i++) {
       for(int j = 0; j < n; j++) {
           cin >> board[i][j];
       }
   }
   vector<int> team(n);
   fill(team.begin()+(n/2), team.end(), 1);
   do {
       int diff = 0;
       for(int i = 0; i < n; i++) {
           for(int j = i+1; j < n; j++) {
               if(team[i] != team[j]) continue;
               if(team[i] == 0) {
                   diff += (board[i][j]+board[j][i]);
               }
               else {
                   diff -= (board[i][j]+board[j][i]);
               }
           }
       }
       mn = min(mn, abs(diff));
   } while(next_permutation(team.begin(), team.end()));
   cout << mn;
}

느낀점

생각을 더 깊게 하고 나은 방법을 찾아 구현하자.
무작정 덤벼들지 말고, 무조건 생각을 하고 풀이하자