[백준 14889] 스타트와 링크

문제 보기

이 문제는 브루트 포스 문제이다.

두 팀의 능력치의 경우의 수를 모두 따져서 그 차이가 최소가 되는 것을 찾아야 한다.

먼저 각 팀을 정확히 절반으로 나누는 과정은 DFS로 구현하였다.

문제를 해결하는 단계는 다음과 같다.

1. n 명의 선수들을 2개 팀으로 나누어서 배치한다. (DFS 적용)

2. 각 팀에서 선수 2 명을 선택하여, 팀에 더해지는 능력치를 구하고, 팀의 총 능력치에 더한다. (조합)

3. 두 팀의 능력치 차이의 최소값을 구한다.

다른 사람들의 풀이를 보아하니, itertools의 combination 함수를 사용한 것을 보았다.

다음에는 나도 itertools를 사용해서 문제를 풀어봐야겠다.

import sys
 
n = int(sys.stdin.readline())
board = [[0 for c in range(n + 1)] for r in range(n + 1)]
for r in range(1, n + 1, 1):
    line = list(map(int, sys.stdin.readline().split()))
    for c in range(1, n + 1, 1):
        board[r][c] = line[c - 1]
 
team_start = list()
team_link = list()
answer = sys.maxsize
 
 
def solution(idx, n):
    if idx == n + 1:
        
        # now we have full teams
        if len(team_start) == len(team_link) == n / 2:
            global answer
            sum_start, sum_link = 0, 0
            
            # get total power of each team with the combination of each team
            for i in range(n // 2):
                for j in range(i + 1, n // 2, 1):
                    player1, player2 = team_start[i], team_start[j]
                    sum_start += board[player1][player2] + board[player2][player1]
                    
                    player1, player2 = team_link[i], team_link[j]
                    sum_link += board[player1][player2] + board[player2][player1]
            answer = min(answer, abs(sum_start - sum_link))
        return
    
    # push i-th player to start team
    team_start.append(idx)
    solution(idx + 1, n)
    team_start.pop()
 
    # push i-th player to link team
    team_link.append(idx)
    solution(idx + 1, n)
    team_link.pop()
 
 
solution(1, n)
print(answer)