14889번: 스타트와 링크
예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다.
www.acmicpc.net
조합으로 N/2개를 뽑은 후에 뽑은 것들의 조합의 능력치를 N^2으로 각각 계산해줍니다.
그 다음 abs(a-b)의 차이의 최소를 구해 출력해주시면 됩니다.
|
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
44
45
46
47
48
49
50
51
52
53
54
|
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Main {
static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
static StringTokenizer st;
static boolean pick[] = new boolean[21];
static int list[][] = new int[21][21];
static int N, ans = Integer.MAX_VALUE;
static void func(int idx, int cnt) {
if (cnt == N / 2) {
int a = 0;
int b = 0;
for (int i = 0; i < N; i++) {
for (int j = i + 1; j < N; j++) {
if (pick[i] == pick[j]) {
if (pick[i])
a += (list[i][j] + list[j][i]);
else
b += (list[i][j] + list[j][i]);
}
}
}
ans = Math.min(ans, Math.abs(a - b));
return;
}
for (int i = idx; i < N; i++) {
pick[i] = true;
func(i + 1, cnt + 1);
pick[i] = false;
}
}
static void input() throws Exception {
st = new StringTokenizer(br.readLine());
N = Integer.parseInt(st.nextToken());
for (int i = 0; i < N; i++) {
st = new StringTokenizer(br.readLine());
for (int j = 0; j < N; j++) {
list[i][j] = Integer.parseInt(st.nextToken());
}
}
}
public static void main(String[] args) throws Exception {
input();
func(0, 0);
System.out.println(ans);
}
}
|
cs |
'algorithm > dfs' 카테고리의 다른 글
| boj 2239 스도쿠 (0) | 2021.04.16 |
|---|---|
| boj 2458 키 순서 (0) | 2021.04.13 |
| boj 2023 신기한 소수 (0) | 2021.03.16 |
| boj 14500 테트로미노 (0) | 2021.03.15 |
| boj 16922 로마 숫자 만들기 (0) | 2021.02.24 |