백준 - 스타트와 링크 (삼성 기출) / Silver 2 / 14889번

문제 📋

백준 삼성기출 - 스타트와 링크

풀이 📝

import sys
from itertools import combinations


cases = []
result = []

n = int(sys.stdin.readline())
table = [list(map(int, sys.stdin.readline().split())) for _ in range(n)]
nums = [i+1 for i in range(n)]
comb = list(combinations(nums, n//2))  # 한개의 팀 인원만큼 선택하는 경우의 수.

for i in range(len(comb)//2):  # 각각 한개의 팀원만큼 선택한 경우의 수에 대하여 짝이 맞도록 2개씩 묶어줌.
    cases.append([comb[i], comb[len(comb)-(i+1)]])

for case in cases:
    target_1 = list(combinations(case[0], 2))  # 한팀에 대하여 점수 계산을 위해 두 선수씩 묶어줌.
    target_2 = list(combinations(case[1], 2))

    team_1_score = sum([table[i[0]-1][i[1]-1] + table[i[1]-1][i[0]-1] for i in target_1])  # 점수 계산
    team_2_score = sum([table[i[0]-1][i[1]-1] + table[i[1]-1][i[0]-1] for i in target_2])

    result.append(abs(team_1_score - team_2_score))

print(min(result))

Brute force 즉, 완전 탐색 문제이다.
먼저 두 개의 팀으로 나눠야 되었는데
전체 인원 N 에서 N//2 수 만큼 선택하는 경우의 수를 먼저 구한 뒤
각각 짝을 맞춰서 2개로 묶어 주었다.

예를 들면 다음과 같다.

[(1, 2), (1, 3), (1, 4), (2, 3), (2, 4), (3, 4)]  # 조합을 구해놓고

[[(1, 2), (3, 4)], [(1, 3), (2, 4)], [(1, 4), (2, 3)]]  # 짝에 맞게 묶어줌.

그 이후에는 각각의 case에 대하여 점수 계산 할 수 있도록 2개의 선수씩 묶어준 뒤
점수를 각각 계산하고 그 차의 절대값을 result 배열에 저장하였다.