[알고리즘] 백준 14889 스타트와 링크 / python

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

14889번: 스타트와 링크

 

def next_permutation(a):
    n = len(a) - 1
    i = n
    while i > 0 and a[i-1] >= a[i]:
        i -= 1
    if i == 0:
        return False
    j = n
    while a[i-1] >= a[j]:
        j -= 1
    a[i-1], a[j] = a[j], a[i-1]
    j = n
    while i < j:
        a[i], a[j] = a[j], a[i]
        i += 1
        j -= 1
    return True

N = int(input())
S = [list(map(int, input().split())) for _ in range(N)]
R = [0 if i < N//2 else 1 for i in range(N)]
ans = 10000000000
while True:
    first, second = [], []
    for i in range(N):
        if R[i] == 0:
            first.append(i)
        else:
            second.append(i)
    r1, r2 = 0, 0
    for i in range(N//2):
        for j in range(N//2):
            if i == j:
                continue
            r1 += S[first[i]][first[j]]
            r2 += S[second[i]][second[j]]
    _min = abs(r1 - r2)
    if _min < ans:
        ans = _min
    if not next_permutation(R):
        break
print(ans)

pypy로 컴파일해야 시간초과가 안뜨는,,😓