백준 14889 스타트와 링크

과정

• 백트래킹 + 브루트포스
• 백트래킹으로 부분 수열 구하기 (팀 나누기)
  • 팀은 두 개로 나뉨
  • 0이 있는 모든 팀의 경우를 구하고 해당 팀에 속하지 않는 인원을 한 팀으로 묶는 방식 사용.
  • 부분 수열 구하는 연산을 반으로 줄일 수 있음.
  • result 리스트에 0을 기본으로 넣고, 시작하는 level과 idx를 1로 해서 함수를 시작하면, 0이 있는 모든 팀의 경우를 구할 수 있음.
• 구한 부분 수열에 대해 점수 차이 구해서 최소값 업데이트
  • 0이 있는 팀을 스타트팀이라고 하면, 링크팀에는 나머지 인원이 모두 들어있음.
  • 이중 반복문을 통해 각 팀의 점수를 구하고, 최소값 업데이트

import sys
input = sys.stdin.readline
N = int(input())
lst = [i for i in range(N)]
map_lst = [list(map(int, input().split())) for _ in range(N)]

result = [0]
min = 10**8
def sub(N, M, level, idx):
    global min
    if level == M:
        link_lst = []
        start = 0
        link = 0
        for i in lst:
            if i not in result:
                link_lst.append(i)
        for i in result:
            for j in result:
                start += map_lst[i][j]
        for i in link_lst:
            for j in link_lst:
                link += map_lst[i][j]

        if abs(start-link) < min:
            min = abs(start-link)
        return
    for i in range(idx, N):
        result.append(lst[i])
        sub(N, M, level+1, i+1)
        result.pop()
# M은 N // 2
sub(N, N//2, 1, 1)
print(min)