[백준] 14889번 스타트와 링크

14889번 스타트와 링크

---

1. 이해하기

• 전체 N명에서 N/2명으로 두 팀을 나눠서 각 팀의 선택된 사람들의 능력치 차이의 최소를 구하는 문제이다.
• 모든 경우를 다 해보는 완전탐색 문제.

---

2. 구현하기

• N명에서 N/2을 고르는 방법을 만든다.

  • 그 후 각 팀에서 고른 사람들의 능력치 차이의 최솟값을 반환한다.

  int solve(int index, int cnt) {
      if(index > N) return MAX;
      if(index == N and cnt == N/2) {
          int sum1 = 0, sum2 = 0;
          for(int i = 0; i < N; i++) {
              for(int j = 0; j < N; j++) {
                  if(i == j) continue;
                  if(selected[i] and selected[j]) {
                      sum1 += ability[i][j];
                  } else if(!selected[i] and !selected[j]) {
                      sum2 += ability[i][j];
                  }
              }
          }
          return abs(sum1-sum2);
      }
  
      int ret = MAX;
      selected[index] = true;
      ret = min(ret,solve(index+1,cnt+1));
      selected[index] = false;
      ret = min(ret,solve(index+1,cnt));
      return ret;
  }

---

3. 전체 코드

#include <iostream>
using namespace std;
const int MAX = 987654321;
int ability[20][20];
bool selected[20];
int N;

int abs(int a) {
    return (a<0)?-a:a;
}

int solve(int index, int cnt) {
    if(index > N) return MAX;
    if(index == N and cnt == N/2) {
        int sum1 = 0, sum2 = 0;
        for(int i = 0; i < N; i++) {
            for(int j = 0; j < N; j++) {
                if(i == j) continue;
                if(selected[i] and selected[j]) {
                    sum1 += ability[i][j];
                } else if(!selected[i] and !selected[j]) {
                    sum2 += ability[i][j];
                }
            }
        }
        return abs(sum1-sum2);
    }

    int ret = MAX;
    selected[index] = true;
    ret = min(ret,solve(index+1,cnt+1));
    selected[index] = false;
    ret = min(ret,solve(index+1,cnt));
    return ret;
}

int main() {
    cin >> N;
    for(int i = 0; i < N; i++) {
        for(int j = 0; j < N; j++) {
            cin >> ability[i][j];
        }
    }

    cout << solve(0,0) << '\n';
    return 0;
}