[백준] 14889번 - 스타트와 링크 (파이썬)

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

# 스타트와 링크
import sys
MAX = sys.maxsize

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

people = [i for i in range(N)]
start_team = []
result = MAX


def chooseMember(num, k):
    global result
    if num == N//2:
        link_team = []
        link_team = list(set(people) - set(start_team))
        result = min(result, abs(getScore(link_team) - getScore(start_team)))
        return
    for i in range(k, N):
        start_team.append(i)
        chooseMember(num+1, i+1)
        start_team.pop()


def getScore(list):
    score = 0
    for node in range(N):
        if node in list:
            for nnode in range(len(arr[node])):
                if nnode in list and node != nnode:
                    score += arr[node][nnode]
    return score


chooseMember(0, 0)
print(result)

 

백트랙킹

1. chooseMember : start팀의 멤버를 고르고 남은 멤버를 link팀에 넣어줘서 getScore를 호출해서 result를 초기화

  - 백트랙킹으로 N//2 만큼 start_team 리스트에 인원을 append한다(N//2명씩 고르는 모든 경우의수)

  - N//2만큼 골랐으면, link_team에 전체사람(people리스트) - start_team을 해준 값을 넣는다(차집합)

  - getScore를 호출하여 각 리스트를 매개변수로 전달 리턴 값은 팀별 점수 이다. 둘의 차의 절대값을 result로

2. getScore : 인원을 전부 체크해서 list에 있으면

  - 그 인원도 체크하고 list에 있고, 자기 자신이 아니면

  - score에 해당 시너지점수(arr값)을 더해준다

  - return score

3. result 출력