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

Algorithm 문제

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

노예2 2019. 7. 17. 01:26

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

14889번: 스타트와 링크

예제 2의 경우에 (1, 3, 6), (2, 4, 5)로 팀을 나누면 되고, 예제 3의 경우에는 (1, 2, 4, 5), (3, 6, 7, 8)로 팀을 나누면 된다.

www.acmicpc.net

brute-force 문제

재귀 함수를 이용하여 풀었다. pypy2를 이용하여 컴파일.

python3 등을 사용하였으면 시간초과가 발생했을 것 같다.

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
import sys
 
diff_min = float("INF")
def make_team(n, stat, depth, team1_arr):
    if sum(team1_arr) == n//2:
        st_1, st_2 = 0, 0
        t1, t2 = [], []
        for idx, team1 in enumerate(team1_arr):
            if team1 == 1:
                t1.append(idx)
            else:
                t2.append(idx)
        
        for idx, m1 in enumerate(t1):
            for m2 in t1[idx+1:]:
                st_1 += stat[m1][m2] + stat[m2][m1]
        for idx, m1 in enumerate(t2):
            for m2 in t2[idx+1:]:
                st_2 += stat[m1][m2] + stat[m2][m1]
 
        global diff_min
        diff_min = min(abs(st_1-st_2), diff_min)
        return
    
    if depth == n:
        return
 
    team1_arr[depth] = 1
    make_team(n, stat, depth+1, team1_arr)
    team1_arr[depth] = 0
    make_team(n, stat, depth+1, team1_arr)
    return
 
 
lines = sys.stdin.readlines()
n = int(lines[0])
stat = []
for line in lines[1:]:
    stat.append(list(map(int, line.split())))
 
team1_arr = [0 for _ in range(n)]
make_team(n, stat, 0, team1_arr)
sys.stdout.write(str(diff_min))
cs