[백트래킹] 스타트와 링크
2021. 8. 30. 17:48ㆍ백준
오랜만에 백준 포스팅을 한다.
천천히 진행되던 백트래킹이 드디어 끝났다.
from sys import stdin
from itertools import combinations as cb
N = int(stdin.readline())
ARR = []
def get_team_status(team_list: list):
total = 0
global ARR
for x, y in cb(team_list, 2):
total = total + ARR[x - 1][y - 1] + ARR[y - 1][x - 1]
return total
for x in range(N):
LINE = list(map(int, list(stdin.readline().split())))
ARR.append(LINE)
team_combination = []
for i in cb(range(1, N + 1), int(N / 2)):
team_combination.append(list(i))
min = 100
for j in range(int(len(team_combination) / 2)):
if min == 0:
break
team_start = team_combination[j]
team_link = team_combination[len(team_combination) - j - 1]
min_now = abs(get_team_status(team_start) - get_team_status(team_link))
if min_now < min:
min = min_now
print(min)