boj_14889.md

BOJ 14889. 스타트와 링크

문제 링크

[BOJ 14889] 스타트와 링크

분류

브루트 포스, 백트래킹

코드

# 스타트와 링크

import sys
from itertools import combinations

# 전체 인원수 input
people_number = int(sys.stdin.readline())

# 보너스 리스트 선언 및 input
bonus_list = []
for _ in range(people_number):
    bonus_list.append(list(map(int, sys.stdin.readline().split())))

# 두 팀의 보너스 차이의 최소값 변수 선언 (초기값 무한대, 비교 후 작은 값으로 반복 갱신)
vs_val = float('inf')

# 전체 인원수를 반으로 갈라서 한 팀 결성
for team in combinations([number for number in range(1, people_number + 1)], people_number // 2):
    # 속하지 않았다면 반대편 팀
    other_team = [member for member in range(1, people_number + 1) if member not in team]
    # 팀 보너스 연산
    team_bonus = 0
    # 팀에서 둘씩 뽑은 값에 대응하는 보너스 전부 추가 (순서쌍 없는 조합이므로 순서 바꾼 값도 추가)
    for duo in combinations(team, 2):
        team_bonus += bonus_list[duo[0] - 1][duo[1] - 1]
        team_bonus += bonus_list[duo[1] - 1][duo[0] - 1]
    # 다른 팀 보너스 연산
    other_team_bonus = 0
    for other_duo in combinations(other_team, 2):
        other_team_bonus += bonus_list[other_duo[0] - 1][other_duo[1] - 1]
        other_team_bonus += bonus_list[other_duo[1] - 1][other_duo[0] - 1]
    # 두 팀의 보너스 차이값과 기존 최소값을 비교해서 작은 쪽으로 갱신
    vs_val = min(abs(team_bonus - other_team_bonus), vs_val)
    # 0보다 작아질 수 없기 때문에 0에 도달했다면 바로 종료
    if vs_val == 0:
        break

# 결과값 출력
print(vs_val)