N명의 사람 (짝수)
각 팀은 반 쪼개서 N/2명씩 구성 -> 스타트팀 링크팀
S_ij : i번사람과 j번 사람이 만났을 때 얻는 에너지
팀의 능력치 = sum(S_ij들)
주의사항 : S_ij와 S_ji는 다를 수도 있다
중요 : i랑 j가 같은 팀에 속했을 때 얻는 에너지는 S_ij + S_ji
해야할것 : 스타트팀 능력치 <-> 링크팀 능력치 차이 최소화
1. 리스트의 인덱스를 가져온다
s = [i for i in range(len(S))]
2. 두 팀으로 나누기 때문에 n/2 만큼만 추출할거
for star in combinations(s, len(s)/2)
3. star에는 인덱스 넘버들이 있으니 나머지 계산해서 link팀 추출
link = s - star
4. star팀 모든 경우의수 계산 => ij ji 더해줌
for a in combinations(star, 2)
aa += S[a[0]][a[1]] + S[a[1]][a[0]]
5. link팀 모든 경우의수 계산 => ij ji 더해줌
for b in combinations(link, 2)
bb += S[b[0]][b[1]] + S[b[1]][b[0]]
6. min값 추출 => 기존 vs star와 link 차이
ans = min(ans, abs(aa-bb))
from itertools import combinations
import sys
input = sys.stdin.readline
leng = int(input())
S = [list(map(int, input().split())) for _ in range(leng)]
#S = [[0, 1, 2, 3], [4, 0, 5, 6], [7, 1, 0, 2], [3, 4, 5, 0]]
#S = [[0, 1, 2, 3, 4, 5], [1, 0, 2, 3, 4, 5], [1, 2, 0, 3, 4, 5], [1, 2, 3, 0, 4, 5], [1, 2, 3, 4, 0, 5], [1, 2, 3, 4, 5, 0]]
#S = [[0, 5, 4, 5, 4, 5, 4, 5], [4, 0, 5, 1, 2, 3, 4, 5], [9, 8, 0, 1, 2, 3, 1, 2], [9, 9, 9, 0, 9, 9, 9, 9], [1, 1, 1, 1, 0, 1, 1, 1], [8, 7, 6, 5, 4, 0, 3, 2], [9, 1, 9, 1, 9, 1, 0, 9], [6, 5, 4, 3, 2, 1, 9, 0]]
ans = 999999
s = [i for i in range(len(S))]
for star in combinations(s, int(len(s)/2)):
aa = 0
bb = 0
# start에는 인덱스 넘버들이 있음
link = list(set(s) - set(star))
for a in list(combinations(list(star), 2)):
aa += S[a[0]][a[1]] + S[a[1]][a[0]]
for b in combinations(list(link), 2):
bb += S[b[0]][b[1]] + S[b[1]][b[0]]
ans = min(ans, abs(aa-bb))
print(ans)
DFS 방식 (중요)
코드 출처 : https://ji-gwang.tistory.com/260
import sys
input = sys.stdin.readline
N = int(input())
array = []
result = 1e9 #결과값 출력을 위한 result값을 문제의 범위를 벗어나는 큰 수로 초기화
visited = [False] * (N + 1) #방문여부를 확인하는 리스트
for _ in range(N):
array.append(list(map(int, input().split())))
def solve(depth, idx):
global result
if depth == (N // 2): # N // 2 번만큼 재귀를 돌면
start, link = 0, 0 #start팀과 link팀 0으로 선언
for i in range(N):
for j in range(i + 1, N): #이중 리스트의 열은 굳이 0부터 돌필요가 없기 때문에 i + 1 로 범위를 좁혀준다.
if visited[i] and visited[j]: #만약 i,j 둘다 방문 했다면
start += (array[i][j] + array[j][i]) #방문한 사람을 스타트팀에 더해준다.
elif not visited[i] and not visited[j]: # 방문 안한 i j 는 링크팀이므로
link += (array[i][j] + array[j][i]) #방문안한 사람을 링크팀에 더해준다
result = min(result, abs(start - link)) #최솟값을 결과값에 대입
for i in range(idx, N):
if not visited[i]: #만약 방문을 안했다면
visited[i] = True #방문으로 처리
solve(depth + 1, i + 1) #재귀를 돈다
visited[i] = False #방문 완료 처리
solve(0, 0)
print(result)