백준 14889번

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

14889번: 스타트와 링크

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

answer = int(1e9)
    

#팀의 능력치 비교
def compare(team1, team2):
    sum_team1 = 0
    sum_team2 = 0

    for i in range(N//2-1):
        for j in range(i+1,N//2):
            sum_team1 += arr[team1[i]][team1[j]] + arr[team1[j]][team1[i]]
            sum_team2 += arr[team2[i]][team2[j]] +arr[team2[j]][team2[i]]

    return abs(sum_team1 - sum_team2)

def select(team1, count, idx):
    global answer

    #link팀 뽑기
    if count == N//2:
        team2 = []
        for i in range(N):
            if i not in team1:
                team2.append(i)
        
        diff = compare(team1, team2)
      #기존값과 비교하여 더 작은 값이 answer
        answer = min(answer, diff)
        return
      
    #start팀 찾기
    for i in range(idx, N):
        if i not in team1:
            team1.append(i)
            select(team1, count+1, i+1)
            team1.remove(i)

select([], 0, 0)
print(answer)

 

1. DFS를 이용하여 첫 번째 팀을 선택해주고

 

2. n/2 명이 선택되면 나머지를 두 번째 팀으로 정해준다

 

3. 팀의 능력치를 비교하고 능력치의 차를 반환한다.

 

4. 최솟값과 비교해준 후 더 작으면 교체