[백준] 15661번(링크와 스타트)

백준 15661번

최종 제출 코드

import sys

input = sys.stdin.readline

# 입력값을 받아준다
n = int(input().rstrip())
matrix = [list(map(int, input().split())) for i in range(n)]

# 원소의 개수는 20개 이하, 각 값은 100 이하이기 때문에 최소값은 200을 초과할 수 없다
min_diff = 20*100

# link와 start의 합집합은 array
array = set([i for i in range(n)])
link = []

# 만들고자 하는 link의 길이를 매개변수로 받는다
def dfs(length, index):

  global min_diff
  
  # 만들고자 했던 link의 길이와 동일해지면 link에 속하지 않는 array의 원소들을 start의 원소로 구성
  # i = link[0] ... link[-1], j = link[0] ... link[-1]
  # 이와 같은 방식으로 규칙에 따른 각각 집합의 합을 구해준다
  # abs(s-a)가 min_diff보다 작을 경우 min_diff = abs(s-a)로 업데이트
  if len(link)==length:

    start = list(array-set(link))
    
    s = sum(matrix[i][j] for i in link for j in link)
    a = sum(matrix[i][j] for i in start for j in start)
    min_diff = min(abs(s-a), min_diff)
    return

  for i in range(index, n):
    link.append(i)
    dfs(length, i+1)
    link.pop()

# 링크나 스타트에 원소가 1개인 경우는 검사할 필요가 없음
# 그래서 원소가 2개인 경우부터 시작하게 작성했으나 채점을 돌려보니
# 오히려 1개로 시작하는 경우가 실행시간이 더 짧았음
for i in range(2, n//2+1):
  dfs(i, 0)

print(min_diff)

◼️ 일반적인 조합을 구하는 문제와 유사

• 약간만 변형하여 집합을 링크와 스타트로 구분하고 두 그룹의 원소의 합을 비교해주면 됨
• link의 길이의 범위는 2 ~ n//2로 설정한다
  ❓ why① : 왜 2부터 시작하는가 - link의 길이가 1인 경우 s의 값은 0이 된다. 그렇게 되면 a의 값은 matrix 전체 원소의 값의 합에서 link에 속하는 원소와의 조합만을 뺀 값이 되기 때문에 abs(s-a)의 값이 절대로 최소값이 될 수 없다.
  ❓ why② : 왜 n//2에서 끝나는가 - link [0, 1], start [2, 3, 4, 5]와 link[2, 3, 4, 5], link [0, 1]의 케이스는 결국 같은 abs(s-a) 값을 가지기 때문에 굳이 두 케이스를 모두 검사할 필요 없음.
• link의 길이가 인수로 전달한 값과 같아지면, array와 link의 차집합을 start로 만들어 각각의 집합에 포함된 원소들을 이용하여 s와 a 값을 구한다.
• min_diff에 abs(s-a)의 최소값을 업데이트한다.