[알고리즘] 백준 14889 스타트와 링크 파이썬

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

 

문제

https://www.acmicpc.net/problem/14889

14889번: 스타트와 링크

 

 

 

문제이해돕기

4일때는

12 / 34 팀 일때 S12+S21 / S34 + S43 인건 알겠는데,

6일때는 ? 

123 /456 팀 일때 S12+S13+S21+S23+S31+S32 / S45+S46+S54+S56+S64+S65 입니다.

 

 

 

접근과정

1. 스타트팀의 모든 조합을 구한다. --> DFS이용하기

2. 전체집합에서 스타트집합을 뺀 여집합을 구한다. --> 링크 팀

3. 그래프에서 알맞은 숫자들을 더해서, 두 팀의 점수차이의 절대값을 계산해서 보관해둔다.

4. 점수차이집합의 최소값을 구한다.

 

 

 

소스코드

N=int(input())
graph=[list(map(int,input().split())) for _ in range(N)]
arr=[]
arr2=[_ for _ in range(N)]
ansArr=[]
def cal_(a,b):
    asum=0
    for i in a:
        for j in a:
            if i==j:
                continue
            asum+=graph[i][j]
    bsum=0
    for i in b:
        for j in b:
            if i==j:
                continue
            bsum+=graph[i][j]
    ansArr.append(abs(asum-bsum))


def dfs():
    if len(arr)==N//2:
        #중복제거로직추가하기
        cal_(arr,list(set(arr2)-set(arr)))
        return
    
    for i in range(N):
        if len(arr)==0 or i >max(arr):
            arr.append(i)
            dfs()
            arr.pop()
dfs()
print(min(ansArr))

 

 

추가사항

1.위의 소스는 123 / 456 과 456/123 을 두 번 계산한다.

   위의 중복제거로직주석 자리에 중복제거로직을 추가하면 시간을 줄일 수 있다.

2. min값이 0일때 0을 출력하고 exit() 을 해버린다. 

   조금이나마 시간절약이 가능해진다.