14889번 스타트와 링크

문제 링크 : www.acmicpc.net/problem/14889

14889번: 스타트와 링크

내 코드의 알고리즘

 1) 인원 수 N이 N/2로 나누어질 수 있는 경우 구하기(같은 수 반복, 같은 경우 중복 없이)

 2) 1)과정으로 구한 경우 list 중 반은 start팀으로 남은 반은 link팀으로 구분

    -> 이때 팀 구분 순서중요 : start팀은 1)경우의 앞에서부터 / link팀은 1)경우의 뒤에서부터

         ex) 1)의 결과가 [0,1], [0,2], [0,3], [1,2], [1,3], [2,3] 이라면

              start팀 : [0,1], [0,2], [0,3]

              link 팀 : [2,3], [1,3], [1,2]

 3) 각 팀의 멤버들의 capacity 총합 구하기

    -> 한 팀의 멤버수를 고려해서 이중 for문 필요 & 팀의 경우의 수만큼 반복 필요

 4) 두 팀의 모든 경우에서의 capacity를 구했다면 경우별 capacity의 차이가 가장 작은 경우 찾기

   -> 이때 어느 팀이 더 큰지는 중요하지 않으므로 abs()를 사용해 절대값으로 구하기

visited = [False for _ in range(21)]
arr = [ -1 for _ in range(21)]
memberList = []
def memberCheck(now:int, N):
    global visited
    global arr
    global memberList
    if(now==(N/2+1)):
        team1 = []
        for i in range(1,now):
            team1.append(arr[i])
        memberList.append(team1)
    else:
        for i in range(0,N):
            if(visited[i]==True):
                continue
            else:
                if(i>arr[now-1]):
                    arr[now] = i
                    visited[i] = True
                    memberCheck(now+1,N)
                    visited[i] = False

import sys
# 총 인원수
N = int(sys.stdin.readline())
# 사람 별 능력치 입력받기
peopleCapa = []
for _ in range(N):
    peopleCapa.append(list(map(int, sys.stdin.readline().split())))
# 팀 나눌 수 있는 경우 나열
memberCheck(1,N)
# 두팀으로 나누기
caseCount = int(len(memberList) / 2)
startT = []
linkT =[]
for i in range(0,caseCount):
    startT.append(memberList[i])
    linkT.append(memberList[(len(memberList)-1)-i])
#팀별 capa합 구하기
memberCapaCalcul = [[0 for _ in range(2)]for _ in range(caseCount)]
for k in range(0,caseCount):
    for i in range(0,int(N/2)):
        for j in range(0,int(N/2)):
            memberCapaCalcul[k][0]+=peopleCapa[(startT[k])[i]][(startT[k])[j]]
            memberCapaCalcul[k][1] += peopleCapa[(linkT[k])[i]][(linkT[k])[j]]
#팀별 capa차이가 가장 작은 경우 구하기
minimum = 1000
for i in range(0,caseCount):
    capaG = abs(memberCapaCalcul[i][1]-memberCapaCalcul[i][0])
    if(minimum>capaG):
        minimum = capaG
print(minimum)