[백준][14889] Combinations을 이용한 풀이

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

14889번: 스타트와 링크

문제에 대한 이해:

선수들의 번호를 통해 주어진 행렬M에서 선수의 능력치를 찾을 수 있다.

1, 2, 4 번의 선수가 한 팀에 속한다면 해당 팀의 능력치는

M[1,2] +  M[1, 4] + M[2, 1] + M[2, 4] + M[4, 1] + M[4, 2], 즉 1, 2, 4로 이룰 수 있는 원소의 수가 2개인 모든 집합에서 첫번째 원소를 행, 두번째 원소를 열로 보고 찾은 수의 합이다. 1번이 2번과 협업할 때, 2번이 1번과 협업할 때, 2번이 1번과 협업할 때 등등을 모두 더한다.

선수들간의 카티션 프로덕트를 구한다고 할 수 있다.

팀의 능력치를 구하는 방법이 이럴 때, 주어진 인원수 N으로 두 개의 팀을 만든다. 두 팀간의 능력치 차이를 최소로 할 경우 우 팀의 능력치 차이를 출력하라.

 

문제풀이:

백트랙킹을 사용할 수 있으나 combinations을 사용하기로 했다.

인원수 N은 반드시 짝수이고 팀은 단 두 개로만 나누므로 한 팀의 인원 수는 N//2가 된다.

선수 전체의 번호 리스트는 list(range(n)) 으로 만들 수 있다.

문제에서는 선수들의 번호가 1부터 시작하고 있으나 인덱싱할 때의 편의를 위해 0부터 시작하게 만들었다.

두 팀을 각각 A팀과 B팀으로 부른다.

combinations(list(range(n)), N//2)를 하면 A팀에 가능한 모든 선수 조합을 구할 수 있다.

그와 동시에 A팀에 속하지 않은 선수는 반드시 B팀에 속하므로

1) 집합 연산을 통해 전체 선수들의 집합에서 A팀의 차집합

2)  A팀 조합을 리스트로 변경하고 not in 연산자를 통해 A팀에 속하지 않은 원소들의 리스트

를 구해 B팀의 조합도 구할 수 있다.

 

그러나 combinations을 사용하면 위의 두 방법을 사용하지 않아도 된다.

N인원을 2개의 팀으로 나눌 때 가능한 모든 A팀의 조합을 구하는 것은

동시에 B팀의 조합을 구하는 것과 같기 때문이다.

 

선수 0, 1, 2, 3 (인덱싱을 편하게 하기 위해 모든 선수의 번호에서 -1을 했다.)를 두 팀으로 나눌 경우 가능한 모든 A팀의 조합을 구하면

캡처 1

[(0, 1), (0, 2), (0, 3), (1, 2), (1, 3), (2, 3)]이 나온다.

A팀이 첫 번째 조합인 0, 1로 이루어져 있다면 B팀은 마지막 조합인 2, 3으로 이루어지며

A팀이 두 번째 조합인 0, 2로 이루어져 있다면 B팀은 뒤에서 두 번째 조합인 1, 3으로 이루어진다.

A팀이 0, 1이고 B팀이 2, 3인 것과 A팀이 2, 3이면서 B팀이 0, 1인 것은 결국 능력치가 똑같다.

조합가능한 모든 경우의 수가 이미 구해져 있다고 볼 수 있다. 결국 combinations로 구해 만든 조합을 리스트로 만들어 반복문으로 0부터 n//2-1까지, -1부터 -n//2까지 인덱싱하여 조합을 구하면 된다.

 

예시코드:

from itertools import combinations 

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

n_ls = list(range(n))
combi_ls = list(combinations(n_ls, n//2))

def get_tot(team):
    tot = 0
    for i in team:
        for j in team:
            tot += matrix[i][j]
    return tot


mini = float("inf")
for x in range(len(combi_ls)//2):
    a = combi_ls[x]
    b = combi_ls[-1-x]
    a_tot = get_tot(a)
    b_tot = get_tot(b)
    diff = abs(a_tot - b_tot)
    if diff == 0:
        mini = 0
        break
    else:
        if mini > diff:
            mini = diff
    
print(mini)