[백준] 14889 스타트와 링크 파이썬

링크 : www.acmicpc.net/problem/14889

 

푸는 방법은 다음과 같습니다.

 

1. 먼저 배열을 입력받습니다

 

2. 4번줄 cases는 N명을 각각 N/2, N/2로 나누었기 때문에 팀이 생길수 있는 경우의 수를 나열해야 합니다.

 

경우의 수를 나열하는데에는 itertools 라이브러리를 이용해 편하게 생성하였습니다.

 

 

저의 경우는 A팀을 생성하면 , 나머지가 B팀이 되도록 만들었습니다.

(6명이라 하면, A팀으로 (0, 2, 4) 가 생성될 경우, 자동으로 B팀은 나머지인 (1,3,5)가 됩니다)

 

3. 최소격차는 임의로 큰 값을 넣어도 되는데, 행렬 1개의 cell 값이 100을 넘지 않는다길래,

 

N*N*100이 최대값이라 생각하고 이보단 작을 거라 생각한 최대값을 넣었습니다.

 

4. 9번 줄에서 case_a 반복문 안에서 A팀이 가지는 스탯의 합을 생성하였고,

 

15번 줄에서 나머지 B팀을 생성하여, B팀이 가지는 스탯의 합을 만들어 비교하였습니다.

import itertools
N = int(input())
arr = [x for x in range(N)]
cases = list(itertools.combinations(arr, int(N/2)))
for i in range(N):
	arr[i] = list(map(int, input().split()))

min_value = 100*N*N
for case_a in cases:
	stat_A = 0
	stat_B = 0
	for x in case_a:
		for y in case_a:
			stat_A += arr[x][y]
	case_b = [x for x in range(N) if x not in case_a]
	for x in case_b:
		for y in case_b:
			stat_B += arr[x][y]
	min_value = min(min_value, abs(stat_A-stat_B))
print(min_value)