[백준/Python] 14889 스타트와 링크

[백준/Python] 14889 스타트와 링크

정답 코드 및 설명

전체 코드

import sys
input = sys.stdin.readline

def cal_diff(start_team, link_team):
    start_power = sum([S[i][j] for i in start_team for j in start_team])
    link_power = sum([S[i][j] for i in link_team for j in link_team])
    return abs(start_power - link_power)

def backtrack(index, team):
    global min_diff
    if len(team) == n // 2:
        start_team = team
        link_team = [x for x in range(n) if x not in start_team]
        diff = cal_diff(start_team, link_team)
        min_diff = min(min_diff, diff)
        return 
    for i in range(index, n):
        if i not in team:
            team.append(i)
            backtrack(i +1, team)
            team.pop()

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

min_diff = float('inf')

backtrack(0, [])

print(min_diff)

코드 설명

def cal_diff(start_team, link_team):
    start_power = sum([S[i][j] for i in start_team for j in start_team])
    link_power = sum([S[i][j] for i in link_team for j in link_team])
    return abs(start_power - link_power)

cal_diff 함수는 s 팀과 l 팀의 팀원의 능력치를 합하고 두 팀의 차이를 반환한다.

def backtrack(index, team):
    global min_diff
    if len(team) == n // 2:
        start_team = team
        link_team = [x for x in range(n) if x not in start_team]
        diff = cal_diff(start_team, link_team)
        min_diff = min(min_diff, diff)
        return 
    for i in range(index, n):
        if i not in team:
            team.append(i)
            backtrack(i +1, team)
            team.pop()

backtarck 함수는 팀을 2개로 나누고 팀이 딱 절반으로 나누어 졌을 때, 차이를 계산하고 최소 값을 저장한다

이를 출력하면 정답이 된다.