Life Engineering
[BOJ 14889] 스타트와 링크(Python3) 본문
from itertools import combinations
N=int(input())
l=[x for x in range(N)]
S=[]
result=int(1e9)
for i in range(N):
S.append(list(map(int, input().split())))
comb=list(combinations(l,N//2))
length=len(comb)//2
for i in range(length):
start=0
link=0
for j in range(N//2):
for k in range(j+1, N//2):
start+=(S[comb[i][j]][comb[i][k]]+S[comb[i][k]][comb[i][j]])
temp=[x for x in l if x not in comb[i]]
for j in range(N//2):
for k in range(j+1, N//2):
link+=(S[temp[j]][temp[k]]+S[temp[k]][temp[j]])
result=min(result, abs(start-link))
print(result)
브루트 포스 알고리즘으로 하나씩 케이스를 계산하여 최소값을 찾는 경우로 했다.
이때 각 경우의 수를 구할 땐 조합을 구하는 라이브러리인 itertools-combinations 를 이용하였다.
'Problem Solving' 카테고리의 다른 글
[BOJ 14502] 연구소 (Python3) (0) | 2021.02.15 |
---|---|
[BOJ 1182] 부분수열의 합 (Python3) (0) | 2021.02.14 |
[BOJ 9205] 맥주 마시면서 걸어가기 (Python3) (0) | 2021.02.14 |
[BOJ 2467] 용액(Python) (0) | 2021.02.13 |
[BOJ 2644] 촌수계산 (Python) (0) | 2021.02.09 |