BOJ14889: 스타트와 링크

작성일

https://www.acmicpc.net/problem/14889

  • 연휴동안 100문제 풀기 (5/100)
  • 단순한 완전탐색 문제, 근데 Combination 재귀 방식을 새롭게 알게되었다.

이게 처음에 구현한 방식

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
#include <bits/stdc++.h>
using namespace std;

int N, arr[21][21], member[21], ans = INT_MAX;

void fillArray() {
  ios::sync_with_stdio(false);
  cin >> N;
  for(int i = 0; i < N; i++)
    for(int j = 0; j < N; j++)
      cin >> arr[i][j];
}

int abs(int n) { return n > 0 ? n : -n; }
int calc(int team) {
  int ans = 0;
  for(int i = 0; i < N; i++)
    for(int j = 0; j < N; j++)
      if(member[i] == team && member[j] == team)
        ans += arr[i][j];
  return ans;
}

void selectMember(int cur, int start) {
  if(cur == N/2) {
    ans = min(ans, abs(calc(0) - calc(1)));
    return;
  }
  if (ans == 0) return;

  for(int i = start; i < N; i++) {
    if(member[i]) continue;
    member[i] = 1;
    selectMember(cur+1, i+1);
    member[i] = 0;
  }
}

int main() {
  fillArray();
  selectMember(0, 0);
  cout << ans;
}

Combinations 의 점화식을 이용한 다른 재귀. 근데 더 느림

1
2
3
4
5
6
7
8
9
10
11
12
13
void comb(int n, int r) {
  if(n < 0) return;
  if(ans == 0) return;
  if(r == 0) {
    ans = min(ans, abs(calc(0) - calc(1)));
    return;
  }

  member[n] = 1;
  comb(n-1, r-1);
  member[n] = 0;
  comb(n-1, r);
}