풀이

1. 먼저 시간복잡도를 통해서 어떻게 팀가치를 계산할지 고민해보자.

최대 인원이 참가했을 때 20명 중 10명을 고르는 경우의 수와 각 경우의 수 마다 팀가치를 계산하는 시간을 계산하면 이는 문제의 정해진 조건보다 작은 것을 알 수 있다.

점수를 계산하는 과정은 two pointer를 사용해서 S 2차원 배열 안에 S[i][j] 로 접근해 계산할 수 있다.

A팀과 B팀을 구분해서, 각각 팀의 합산 점수를 계산하면 된다.

2. 팀을 어떻게 구분할까?

A팀 인원만큼 뽑게 되면 당연히 자동으로 나머지는 B팀이 되기 때문에 A팀을 N/2 만큼 뽑았을때 나머지 뽑히지 않은 사람들을 B팀으로 계산하면 된다.

백트래킹에서 재귀호출하기 이전에 A팀에 넣었다는 의미로 visited배열에 해당 id를 True로 처리하면 2중 for문 하나로 A팀과 B팀의 score를 한번에 계산할 수 있다.

for i in range(idx,N):
	visited[i] = True
    dfs(L+1,i+1)
    visited[i] = False

위와 같이 dfs 재귀하기 전에 visited처리를 해서 A라는 것을 기록해두고,

for i in range(N):
	for j in range(N):
		if visited[i] and visited[j]:
			team_a_score+=S[i][j]
		elif not visited[i] and not visited[j]:
			team_b_score+=S[i][j]

위와 같이 2중 for문으로 visited인지 아닌지 확인해가며 A팀과 B팀의 점수를 한번에 계산할 수 있다.

• 두 인덱스 모두 visited이면 A팀
• 두 인덱스 모두 visited아니면 B팀

3. 두 팀 인원수를 선택하는 경우의 수를 어떻게 설정한 것인가?

[1,2,3,4] 가 참여했다고 가정한다면, [1,2]과 [2,1]은 같은 조합임을 의미한다.

따라서 중복을 제거하기 위해서 새로 뽑을 인원수를 뽑을 때, 재귀 호출되기 이전의 선수번호보다 무조건 큰 번호부터 고려해서 뽑는 것이다.

for i in range(idx,N) # idx : 이전에 뽑은 사람번호+1 인 수

위와 같이 for문을 구현한 이유이다.

dfs(0, 0)
├── i = 0 (선수 1 선택)
│   └── dfs(1, 1)
│       ├── i = 1 (선수 2 선택) → 팀 A: [1, 2]
│       ├── i = 2 (선수 3 선택) → 팀 A: [1, 3]
│       └── i = 3 (선수 4 선택) → 팀 A: [1, 4]
├── i = 1 (선수 2 선택)
│   └── dfs(1, 2)
│       ├── i = 2 (선수 3 선택) → 팀 A: [2, 3]
│       └── i = 3 (선수 4 선택) → 팀 A: [2, 4]
├── i = 2 (선수 3 선택)
│   └── dfs(1, 3)
│       └── i = 3 (선수 4 선택) → 팀 A: [3, 4]
└── i = 3 (선수 4 선택)
    └── dfs(1, 4) → 종료 (i=N 이므로 루프 없음)

위와 같은 순서로 함수가 동작하게 된다.

전체 코드는 아래와 같다.

import sys
N=int(input())
stack=[]
visited=[0]*(N+1)
S=[list(map(int,input().split())) for _ in range(N)]
min_num=sys.maxsize

def dfs(L,idx):
    global min_num
    if L==N//2:


        team_a_score=0
        team_b_score=0
        for i in range(N):
            for j in range(N):
                if visited[i] and visited[j]:
                    team_a_score+=S[i][j]
                elif not visited[i] and not visited[j]:
                    team_b_score+=S[i][j]
                
        min_num=min(abs(team_a_score-team_b_score),min_num)
        return
        # print(team_a_score,team_b_score,a_team, b_team)

    for i in range(idx,N):
        visited[i] = True
        dfs(L+1,i+1)
        visited[i] = False
        
dfs(0,0)
print(min_num)