1. 문제

---

출처: 백준 14889번

2. 풀이

---

가능한 팀 조합을 뽑고, 각 조합에 따른 점수 계산을 하고 최솟값을 찾는 순으로 풀이를 할 수 있다.

1. 팀 조합 만들기

가능한 팀 조합을 만드는 것은, 백준 15649번 N과 M (1) 에서 사용했던 방법을 이용하면 된다.

DFS를 이용해서 순열을 찾는 것인데, 이번에는 점수 계산을 위해 해당 순열을 리스트에 저장해둬야 한다. 이 때, list(lst)를 하지 않고, 단순하게 lst를 append했더니 오류가 발생했었다.

재귀적으로 DFS 함수를 사용하면서 해당 리스트도 재사용을 하다 보니, 새롭게 주솟값을 할당해 주지 않으면 원하는 그 순간의 순열을 저장하지 못해서 발생하는 오류인 듯하다.

2. 각 조합에 따른 점수 계산과 최솟값 찾기

첫 번째 팀의 점수를 저장되어 있는 순열(팀 조합)을 이용해서 계산한다.
두 번째 팀은 set을 활용해서 쉽게 얻어낼 수 있으니, 두 번째 팀도 점수 계산을 한다.

가능한 모든 팀 조합에 대해서 두 팀 간의 점수 차이를 구하고 최솟값을 출력한다.

이 과정에서 굉장히 for문을 많이 사용하게 되어서, 시간 복잡도가 높은 편이다.

Python 3로 제출할 경우, 시간 초과가 되니 PyPy3로 제출해야 한다.

3. 소스코드

---

import sys
input = sys.stdin.readline

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

#다양한 팀 조합을 만들어내는 DFS 함수
lst_total = []
lst = []
def dfs(N):
    if len(lst) == N//2:
    	#여기서 list(lst) 해주지 않으면, lst값이 딱 이 때 것이 들어가지 않고 계속 재사용되서 오류가 난다.
        lst_total.append(list(lst))
        return
    else:
        for i in range(N):
            if i not in lst:
                if len(lst) > 0 and i < lst[-1]:
                    pass
                else:
                    lst.append(i)
                    dfs(N)
                    lst.pop()
                
dfs(N)

min_value = 20*100
for i in range(len(lst_total)):
	# 첫 번째 팀의 점수 계산
    temp = 0
    for j in range(N//2):
        for k in range(N//2):
            temp += score[lst_total[i][j]][lst_total[i][k]]
    
    # 두 번째 팀의 점수 계산
    temp2 = 0
    lst2 = set(range(N)) - set(lst_total[i])
    lst2 = list(lst2)
    for j in range(N//2):
        for k in range(N//2):
            temp2 += score[lst2[j]][lst2[k]]
    
    # 팀 조합에 따른 점수 차이 비교
    diff = abs(temp-temp2)
    if diff < min_value:
        min_value = diff
        
print(min_value)

4. 그 외

---

점수를 계산하는 과정에서 for문을 너무 많이 사용하는 듯해서, 더 짧게 할 수 있는 방법이 있다면 좋을 것 같다.