[백준] 14889번(python 파이썬)

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

 

풀이

 

먼저 백트래킹을 이용하여 n/2 개의 수를 이루는 조합을 구한다.

ex) n = 4 (1, 2) (1, 3) (1, 4) (2, 3) (2, 4) (3, 4)

 

백트래킹을 이용하여 쉽게 구할수 있다.

구하는 도중 새로운 숫자가 들어오면 원래 있던 숫자와 S[i][j] + S[j][i]를 구한다.

ex) (1) 에서 2가 들어옴 (1, 2) 이때 S[1][2] + S[2][1]를 구해주고 결과값을 매개변수로 넘겨줌

ex) (1, 2) 에서 3이 들어옴 (1, 2, 3) 이때 1,2에 대한 합은 구해줬으니 그 값과 S[1][3] + S[3][1], S[2][3] + S[3][2]을 반복문을 통해 더해줌... 

(말로 설명하는게 진짜 어려운거같다...)

 

이렇게 구하면 각 조합별로 구한값이 deque()에 들어간다.

양 사이드의 값들이 팀을 나눴을때 각 팀의 능력 값이다.

ex) deque = [1,2,3,4,5,6,7,8] 이라면 (1, 8) (2, 7) (3, 6) (4, 5)

 

이제 최소값을 구하면된다....

 

 

코드

from collections import deque

n = int(input())
s = [list(map(int, input().split())) for _ in range(n)]

visited = [False] * (n + 1)
team = list()
result = deque()

def BackTracking(start, depth, person_sum):
    if depth == n // 2 + 1:
        result.append(person_sum)
        return
    for i in range(start, n+1):
        if visited[i]:
            continue

        visited[i] = True
        team.append(i)
        BackTracking(i, depth + 1, PersonSum(person_sum, team, i))
        team.pop()
        visited[i] = False

def PersonSum(person_sum, team, i):
    for person in team:
        person_sum += Solve(person, i)
    return person_sum

def Solve(i, j):
    return s[i-1][j-1] + s[j-1][i-1]

def Result(result : deque):
    result_min = 1e9

    for i in range(len(result) // 2):
        team1 = result.popleft()
        team2 = result.pop()
        result_min = min(result_min, abs(team1 - team2))

    return result_min

BackTracking(1, 1, 0)
print(Result(result))