[Python] BOJ 14889 - 스타트와 링크

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

14889번: 스타트와 링크

# 2017 삼성SW역량 테스트에 출제된 문제이다.

 

# BT함수는 백트래킹을 이용해 N//2명으로 이루어진 '링크'팀을 구해서 answer에 append해준다.

 

# lst는 전체 인원중에서 answer에 있는 '링크'팀을 빼면 '스타트'팀이 자동으로 구해지기 때문에

   set자료형을 사용하였다.

 

1. lst에 1번부터 N번까지 선수들을 넣고 BT(1, 1, [0])을 실행해 answer에 '링크'팀이 될 수 있는

   모든 경우의 수를 넣은 뒤 start에 lst에서 '링크'팀을 뺀 인원들을 넣어준다.

 

2.  반복문을 돌며 start팀에 있는 사람들의 능력치 합과 link팀에 있는 사람들의 능력치 합을 구하고

    두 능력치의 최솟값을 출력하면 끝

 

import sys
input = sys.stdin.readline
def BT(people, prev, power_sum):
	if people == N // 2:
		answer.append(set(power_sum.copy()))
		return

	for i in range(prev, N):
		power_sum.append(i)
		BT(people + 1, i+1, power_sum)
		power_sum.pop()

N = int(input())
power, answer = [], []
for _ in range(N):
	l = list(map(int,input().split()))
	power.append(l)

lst = {i for i in range(N)}
BT(1, 1, [0])
dab = 99999
for i in answer:
	start = list(lst - i)
	link = list(i)
	link_sum, start_sum = 0, 0
	for j in range(len(start) - 1):
		for k in range(j, len(start)):
			start_sum += power[start[j]][start[k]] + power[start[k]][start[j]]
	for j in range(len(link) - 1):
		for k in range(j, len(link)):
			link_sum += power[link[j]][link[k]] + power[link[k]][link[j]]
	dab = min(abs(start_sum - link_sum), dab)

print(dab)