링크와 스타트 풀이

문제 링크: https://www.acmicpc.net/problem/15661

백준 알고리즘 기초 2/2 530에서 5번째 - 15661번 링크와 스타트를 풀어보았다.

 

풀이: 스타트와 링크에서 좀 더 나아간 문제이다.

파이썬의 경우, 구글링 해서 나온 풀이가 죄다 시간초과를 먹어서 파이썬으로 푼 사람들의 코드를 보다가 찾은  https://www.acmicpc.net/source/54531477 를 참고해서 풀었다.

 

C++

 

Python

from itertools import combinations

def diffs(st,li):
	ss,sl=0,0
	for i,j in combinations(st,2):
		ss+=arr[i][j]+arr[j][i]
	for i,j in combinations(li,2):
		sl+=arr[i][j]+arr[j][i]
	return abs(ss-sl)

n=int(input())
arr=[list(map(int,input().split())) for i in range(n)]
visit=list(range(n))
cnt=10000000
for i in range(1,n//2+1):
	st=list(combinations(visit,i))
	li=list(combinations(visit,n-i))
	leng=len(st)
	for j in range(leng):
		diff=diffs(st[j],li[leng-j-1])
		cnt=min(cnt,diff)
print(cnt)

Java