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

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

14889번: 스타트와 링크

 

brute-force 문제

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

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

 

<Python 코드>

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))