BOJ 14889: 스타트와 링크 (Python3)

오늘의 문제는 DFS와 브루트포스를 함께 사용하는 문제이다.

 

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

14889번: 스타트와 링크

 

이 문제에서 포인트는 '같은 팀의 팀원에 따라서 개인의 능력치가 달라진다'이다.

그렇기 때문에 각 팀의 팀원을 설정하고, 이 때의 두 팀의 능력치의 합의 차이를 구하는 방식으로 해결해보았다.

문제에 주어진 예시를 보면, 

이와 같은 식으로 해결할 수 있다.

각 팀의 능력치의 합이 6이기에, 차는 0이다.

 

def dfs(start,depth):
    global minDiff
    if depth==peopleEachTeam and star[0]:
        power1,power2=0,0
        for i in range(n):
            for j in range(n):
                if star[i] and star[j]:
                    power1+=data[i][j]
                elif not star[i] and not star[j]:
                    power2+=data[i][j]
        minDiff= min(minDiff, abs(power1-power2))
        return
    for i in range(start,n):
        if not star[i]:
            star[i]=True
            dfs(i+1,depth+1)
            star[i]=False
n=int(input())
peopleEachTeam=n//2
data=[]
for _ in range(n):
    data.append(list(map(int,input().split())))
star=[False]*n 
minDiff=1e9
dfs(0,0)
print(minDiff)

 

각 팀이 peopleEachTeam, 즉 모든 인원이 절반으로 균등하게 팀을 이루었을 때,

그때의 각 팀의 능력치의 합을 구하고, 서로 뺀다.

이때, 차이가 제일 작으면, minDiff에 저장을 한다.

처음 if문에 star[0]을 붙인 이유는, start 팀이나 link팀 중 어느 팀에 있는, 팀원들의 능력치가 바뀌지 않기 때문이다.

(스타트 팀 1,2번, 링크님 3,4번 == 스타트팀 3,4번, 링크팀 1,2번)

그렇기 때문에 맨 첫번째 선수가 스타트 팀에 있을 때만 계산을 해도, 합이 상관 없이 나온다. (계산의 수가 절반으로 줄게 된다.)

 

질문은 댓글로 부탁드립니다!