백준_15661_링크와 스타트

문제

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

15661번: 링크와 스타트

풀이

1. make team

팀1이 가질수 있는 선수들의 경우의 수를 구한다.

선수의 수를 n//2로 둔 이유는 중복을 제거하기 위해서이다. (아래 두 경우를 같게 취급)

team1	team1	team1	team2	team1	team1	team2
team2	team2	team2	team1	team2	team2	team1

2. calculation diff ability

두팀의 능력값을 계산해 차이를 구한다.

코드

import sys
from itertools import combinations
input = sys.stdin.readline

N = int(input().strip())
board = [list(map(int, input().strip().split())) for i in range(N)]

# 2. calculation diff ability
def getAbility(selection) :
    ability = 0
    for i in range(N) : 
        for j in range(i, N) :
            it = board[i][j]+board[j][i]
            isTeam1 = selection[i]==True and selection[j]==True
            isTeam2 = selection[i]==False and selection[j]==False
            ability += it*isTeam1 - it*isTeam2
    return abs(ability)

# 1. make team
ans = float('INF')
for np in range(N//2) :
    combi = list(combinations(range(N), np+1))
    for playerList in combi : 
        selection = [False, ]*N
        for player in playerList : 
            selection[player] = True
        ans = min(ans, getAbility(selection))
        

print(ans)