[BOJ-14889] 스타트와 링크

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

14889번: 스타트와 링크

---

[풀이]

(1) 스타트팀원을 구한다.

스타트팀=> 조합 라이브러리를 이용하여 N//2명의 구성원으로 이루는 경우의수를 구한다.

링크팀=> 전체인원1~N 중 스타트팀에 있는 멤버를 제외한 나머지 번호를 의미한다 (filter을 사용했다)

 

(2) 각 팀의 능력치를 구하여, 두 능력치 차이의 최솟값을 구한다. 

과정 (1)에서 구한 스타트팀의 경우의 수를 START에 저장하고

링크팀의 경우의 수를 LINK에 저장했다.

 

START와 LINK의 각 원소인 starts, links은 N//2명의 팀원으로 구성되어있고

starts의 멤버와  links의 멤버가 겹치는 경우는 존재하지 않는다. ( 과정(1) 때문이다.)

 

각 팀의 능력치는 i번 사람과 j번사람이 서로 같은 팀인 경우에만 더해져서 커질 수 있다.

이러한 점을 고려하여 starts에 속한 2명의 팀원을 골라야한다.

나의 경우에는 2중 for문을 사용하여, starts 속한 팀원 2명을 구했다.

 

starts의 팀원구성이 (1,2,3)이라 하면

(1,2) (2,1)

(1,3) (3,1)

(2,3) (3,2)

이렇게 세가지 의 경우를 구할 수 있다.

따라서 위의 예시에 따른 스타트팀의 능력치는

( S[1][2]+S[2][1] ) + ( S[1][3]+S[3][1] ) + ( S[2][3]+S[3][2] ) 이다.

 

링크팀도 위와 동일한 방법으로 능력치를 구했다.

 

모든 starts와 links 에서 두팀의 능력치 차이를 구해서 가장 최솟값을 찾았다.

---

[코드 Python]

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

N=int(input().strip())
S=[ [*map(int, input().strip().split())] for _ in range(N)]
members=[*range(1,N+1)]

# member중 절반으로 나눠서
# 동일 인원수의 스타트팀과 링크팀을 나누는 케이스
START=[*comb(members, N//2)]
LINK=[ [*filter(lambda x: x not in start  ,members)] for start in START]

min_diff=float('inf')
for starts, links in zip(START, LINK):
    start_ability=0
    link_ability=0
    for i in range( N//2 -1):
        for j in range(i+1, N//2):
            start_ability+=(S[starts[i]-1][starts[j]-1]+S[starts[j]-1][starts[i]-1])
            link_ability+=(S[links[i]-1][links[j]-1]+S[links[j]-1][links[i]-1])
    min_diff=min(min_diff, abs(start_ability-link_ability))

print(min_diff)