✍️ 풀이
조합
을 사용해 스타트
팀의 후보자를 구한다.
- 나머지 조합은
링크
팀의 후보자이다.
- 조합에서 2명을 뽑은 조합에서 합을 구한다.
스타트
왈 링크
팀의 총합의 차를 구한다.
- 해당 과정을 구한 조합만큼 반복한다.
🛠 코드
from itertools import combinations
N = int(input())
board = []
for _ in range(N):
board.append(list(map(int,input().split())))
num_list = list(range(N))
res = float('inf')
def solve():
global res
for cand in combinations(num_list,N//2):
start_mem = list(cand)
link_mem = list(set(num_list) - set(cand))
start_comb = list(combinations(start_mem,2))
link_comb = list(combinations(link_mem, 2))
start_sum = 0
for x, y in start_comb:
start_sum += (board[x][y] + board[y][x])
link_sum = 0
for x, y in link_comb:
link_sum += (board[x][y] + board[y][x])
res = min(res, abs(start_sum - link_sum))
solve()
print(res)
✍️ 다른 풀이
- DFS를 통해 총 인원의 반(N/2)을 선택할 때 까지 함수 진입
- select가 1이면
스타트
0이면 링크
로 구분할 수 있다.
- 인원의 반을 선택했다면(if cnt == n//2)
i, j
모두 1이라면 start팀을 증가시키고 모두 0이라면 link팀을 증가시킴
- 두 팀의 능력치 차를 최솟값에 기록
- 이 과정을 모든 DFS가 끝날 때 까지 반복.
🛠 다른 코드
import sys
input = sys.stdin.readline
def dfs(idx, cnt):
global ans
if cnt == n // 2:
start, link = 0, 0
for i in range(n):
for j in range(n):
if select[i] and select[j]:
start += a[i][j]
elif not select[i] and not select[j]:
link += a[i][j]
ans = min(ans, abs(start - link))
for i in range(idx, n):
if select[i]:
continue
select[i] = 1
dfs(i + 1, cnt + 1)
select[i] = 0
n = int(input())
a = [list(map(int, input().split())) for _ in range(n)]
select = [0 for _ in range(n)]
ans = sys.maxsize
dfs(0, 0)
print(ans)
📝 정리
조합
을 쓴다고 무조건 안풀리진 않는다. 적절히 사용하자.
- 순서를 선택할 때
DFS
로 구하는 것은 쓸만 한 것 같다.
🎈 참조