백준 14889번 <스타트와 링크>

백준 알고리즘 14889번

https://www.acmicpc.net/problem/14889

14889번: 스타트와 링크

---

14889번

짝수인 N/2명씩 팀을 나눠 축구 경기를 하려고 한다. i번 사람과 j번 사람이 한 팀에 있을 때의 능력치가 주어졌을 때, 두 팀의 팀 능력치 차이가 최소인 값을 구하여라.

 

입력으로 첫 줄에 사람의 수 N이 들어오고 그 다음 줄에 능력치가 주어진다.

 

출력으로 두 팀으로 나누었을 때, 능력치 차이가 최소인 값을 구해서 출력하면 된다.

---

문제 해결

문제를 봤는데 조합을 만들어서 팀을 구성하는 모든 경우를 확인해야겠다고 생각했다. (N이 최대 20이라 가능한 거 같다.)

 

N명에서 N//2명을 뽑아 start 팀을 만들고 거기에 없는 사람들을 link 팀이라고 한다.

start 팀과 link 팀에 대해 각각 팀 총 능력치를 구한다. 이는 이중 for문을 이용하여 구할 수 있다. 모든 쌍의 능력치를 더해줘야 한다. 이때 (i, j)와 (j, i) 둘 다 더해줘야 한다.

구한 팀 총 능력치의 차이를 구하고 이 값 중 최솟값을 구한다.

---

코드

from itertools import combinations
from re import A
n = int(input())
skill = [list(map(int, input().split())) for _ in range(n)]
idx = [i for i in range(n)]

combi = list(combinations(idx, n//2))

def team(start, idx, skill):
  link = [x for x in idx if x not in start]
  start_score = score(start, skill)
  link_score= score(link, skill)
  return abs(start_score - link_score)

def score(member, skill):
  acc = 0
  size = len(member)
  for i in range(size-1):
    for j in range(i, size):
      acc += skill[member[i]][member[j]] + skill[member[j]][member[i]]
  return acc

answer = 100
for start in combi:
  temp = team(start, idx, skill)
  answer = min(answer, temp)
print(answer)

---

결과

---

완전 탐색 말고 다른 방법으로 푸는 방법이 있다는데 아직 모르겠다,,,