[ BOJ ] 스타트와 링크

/  제출  1  /

 

from itertools import combinations

n = int(input())
s = [list(map(int,input().split())) for _ in range(n)]

teamA = list(combinations(range(n), n//2))
teamB = []
for a in teamA:
  b = []
  for i in range(n):
    if i not in a:
      b.append(i)
  teamB.append(tuple(b))
  

diff = 100
for a, b in zip(teamA, teamB):
  levA = 0
  levB = 0
  playerA = list(combinations(a, 2))
  playerB = list(combinations(b, 2))
  for i, j in playerA:
    levA += s[i][j] + s[j][i]
  for i, j in playerB:
    levB += s[i][j] + s[j][i]
  if abs(levA-levB) <= diff:
    diff = abs(levA - levB)
print(diff)

: 풀이 소요 시간 50분

 

: 문제 레벨에 비해 시간이 많이 소요되었습니다.

: 첫 번째 떠올린 아이디어는 조합으로 모든 경우의 수를 뽑아 능력치 순으로 나열시킨 뒤에 중간값 2개를 값 비교하는 것이었습니다. 뭔소리야 싶을만큼 문제와 전혀 다른 풀이였습니다. 한 20분만에 코드는 써내려 갔는데 원하는 정답이 물론 나오지 않았습니다.

: 두 번째 다시 생각했습니다. 일단 팀 후보들을 완전히 만들어주자. 그러고 전부 계산하자. 비효율적인 느낌이 있지만 우선 구현이 먼저다! 라고 생각하고 나온 것이 위의 풀이입니다. 채점에 2-3분이 걸린 것 봐서는 효율적이지 않은 느낌이어서 불안불안해하며 다른 분들 풀이 확인하고 공부해보겠습니다.