[Algorithm] 백준 14889 - 스타트와 링크 in Python(파이썬)

💡 백준 14889:

두 팀의 조합을 전부 순회하며 팀별 합의 차 탐색

🌱 코드 in Python

알고리즘: Brute Force

import sys
from itertools import combinations

input = sys.stdin.readline
n = int(input())
g = [list(map(int, input().split())) for _ in range(n)]
p = [i for i in range(n)]

ret = 10000 # 최대로 날 수 있는 차
t = list(combinations(p, n//2)) # 전체 조합 경우
c = len(t)
k = 0
for t1 in t:
	if k == c / 2: # 조합 길이의 절반만 탐색
		break
	s = 0
	l = 0
	t2 = list(set(p) - set(t1)) # t1의 차집함으로 두번째 팀 리스트 만들기
	for i in list(combinations(t1, 2)): # t1에서 다시 팀원 조합
		s += g[i[0]][i[1]] 능력치 합산
		s += g[i[1]][i[0]]
	for i in list(combinations(t2, 2)): # t2에서 다시 팀원 조합
		l += g[i[0]][i[1]]
		l += g[i[1]][i[0]]
	tmp = abs(s - l) # 능력치 차이 계산
	if tmp < ret: # 능력치 차가 최소일 때 갱신
		ret = tmp 
	k += 1
print(ret)

이번 문제는 조합을 사용하며 풀면 쉽게 풀 수 있는 문제였다
다만 조합으로 한 팀의 구성원을 선택할 경우 그의 차집합이 되는 두번째 팀을 구하는 방식을 잘 모르겠어서 냅다 for문을 돌리다 이건 아닌 거 같아서 방법을 찾게 되었는데
t2 = list(set(p) - set(t1)) 과 같은 방식으로 구할 수 있었다

이렇게도 list를 만들 수 있다니 그저 신기!

그리고 전체 조합 경우 t에서 먼저 선택 된 t1의 차집합이 t2다 보니
나는 t 길이의 절반만 순회하도록 k라는 변수를 따로 두었는데

for i in range(len(t) // 2):
	t1 = t[i]
    t2 = t[-i-1]

과 같이 구하는 방식도 나중에 알게 되었다
아주 깔끔한 듯!

🧠 기억하자

1. 조합
   • from itertools import combinations 로 사용 가능!
2. 차집합
   • set(p) - set(t1): list 끼리는 - 연산이 안된다!

백준 14889 바로가기