BOJ 14889. 스타트와 링크 (Python)

i,j가 함께 팀이 되었을때의 능력치는 S[i][j] + S[j][i]이다. 두팀의 능력치 합이 최소가 되는 경우를 구하라

기본적인 조합 문제였던 것 같다.
N명의 사람들을 어떻게 반으로 나누는 모든 조합을 구할까 고민이 가장 컸는데, DFS를 이용해서 조합을 구하고, 전체 인원에서 해당 조합을 빼는 방식을 쓰기 위해서 리스트를 set으로 변환해줬다.

조건은 간단하다

• S에는 i가 j와 내는 능력치 S[i][j]가 저장되어있다.
• S[i][j] 는 S[j][i]와 다를 수 있다.

우선 DFS를 이용하여 조합을 구한다.

def dfs(start, array, count):
  global N, grid, team_list, minScore

  if count == N//2:
    team_list.append(set(tuple(array)))
    return
  
  for x in range(start, N):
    dfs(x + 1, array + [x], count + 1)

그다음 각 조합별로 전체 선수의 set에서 빼서 start팀 link팀을 따로 구성하여 점수합 차를 구한다.

eam_list = []
min_score = float("inf")
dfs(0, [], 0)
all_player = set(tuple([x for x in range(N)]))

for start in team_list:
  score_start, score_link = 0, 0
  link = tuple(all_player - start)
  start = tuple(start)

  for i in range(N//2):
    for j in range(N//2):
      if i == j:
        continue
      score_start += grid[start[i]][start[j]]
      score_link += grid[link[i]][link[j]]
  
  min_score = min(min_score, abs(score_start - score_link))

이렇게 하면 꽤나 간단하게 구할수가 있다.

전체코드는 아래와 같다.

import sys

def InputData():
  readl = sys.stdin.readline
  N = int(readl())
  grid = [list(map(int, readl().split())) for _ in range(N)]

  return N, grid

def dfs(start, array, count):
  global N, grid, team_list, minScore

  if count == N//2:
    team_list.append(set(tuple(array)))
    return
  
  for x in range(start, N):
    dfs(x + 1, array + [x], count + 1)


N, grid = InputData()
team_list = []
min_score = float("inf")
dfs(0, [], 0)
all_player = set(tuple([x for x in range(N)]))

for start in team_list:
  score_start, score_link = 0, 0
  link = tuple(all_player - start)
  start = tuple(start)

  for i in range(N//2):
    for j in range(N//2):
      if i == j:
        continue
      score_start += grid[start[i]][start[j]]
      score_link += grid[link[i]][link[j]]
  
  min_score = min(min_score, abs(score_start - score_link))

print(min_score)