[백준 문제] 14889번 스타트와 링크 (파이썬)
[백준 문제] 14889번 스타트와 링크 (파이썬)
[백준 문제] 14889번 스타트와 링크를 풀어본다.
나의 생각의 흐름
- 조합을 쉽게 짤 수 있는 방법을 찾으려 했으나 쉽지 않음
- 잘 생각해보니 조합의 수가 n이 최대 20이어도 그렇게 크지 않을 것 같다라는 생각
- intertools 조합을 이용해서 전체를 다 브루트포스하는 방법 사용
- python3에서는 시간 초과가 나오지만, pypy3에서는 성공
내 풀이 (pypy3으로 성공)
# intertools 패키지로 조합 구하기 위함
from itertools import combinations
import sys
# 멤버들의 index 리스트화
n = int(sys.stdin.readline())
member_lst = list(i for i in range(n))
# 점수 매트릭스 만들기
score_map = []
for _ in range(n) :
score_map.append(list(map(int, sys.stdin.readline().split())))
# 팀으로 나누기 위한 조합을 구함 전체 멤버에서 반으로 가를 수 있는 리스트
member_divide_lst = list(combinations(member_lst,int(n/2)))
# 풀이법
min_diff = 1000000000
for i in range(len(member_divide_lst)): # (nCn/2)/2 개
start_team_lst = list(member_divide_lst[i])
link_team_lst = list(set(member_lst) - set(member_divide_lst[i]))
start_team_all_sum = 0
link_team_all_sum = 0
for j in range(int(n / 2)):
for k in range(int(n / 2)):
start_team_sum = score_map[start_team_lst[j]][start_team_lst[k]]
link_team_sum = score_map[link_team_lst[j]][link_team_lst[k]]
start_team_all_sum += start_team_sum
link_team_all_sum += link_team_sum
diff = abs(start_team_all_sum - link_team_all_sum)
min_diff = min(min_diff, diff)
print(min_diff)
