순열, dfs 모두 가능

bm을 이용해 dfs로 풀었다.


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
#include <stdio.h>
#include <algorithm>
using namespace std;
 
int n, s[20][20], ans = 2e9;
 
void solve(int bm, int x, int cnt) {
    if (cnt > n / 2 || x >= n) return;
    if (cnt == n / 2) {
        int sum[2] = { 0, }, b[20];
        for (int i = 0; i < n; i++) b[i] = bm&(1 << i) ? 1 : 0;
        for (int i = 0; i < n; i++) {
            for (int j = i + 1; j < n; j++) {
                if (b[i] != b[j]) continue;
                sum[b[i]] += s[i][j];
                sum[b[i]] += s[j][i];
            }
        }
        ans = min(ans, abs(sum[0] - sum[1]));
        return;
    }
    solve(bm | (1 << x), x + 1, cnt + 1);
    solve(bm, x + 1, cnt);
}
 
int main() {
    scanf("%d", &n);
    for (int i = 0; i < n; i++) for (int j = 0; j < n; j++)
        scanf("%d", &s[i][j]);
    solve(0, 0, 0);
    printf("%d", ans);
    return 0;
}
cs


저작자표시 비영리 변경금지

'BOJ' 카테고리의 다른 글

14891 톱니바퀴  (0) 2017.10.26
14890 경사로  (0) 2017.10.26
14888 연산자 끼워넣기  (0) 2017.10.26
14648 쿼리 맛보기  (0) 2017.10.03
8068 Water  (0) 2017.10.03

+ Recent posts

티스토리툴바