[Python][백준] 14889번 스타트와 링크

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

공부 날짜 : 2022.09.02
정답 참조 여부 : X

축구 경기할 때 실력차이가 최소가되는 조합을 찾고 그 최소값을 찾는 문제이다.

처음 문제를 읽고 풀이 방법이 바로 떠오르지 않았다. 가장먼저 nCn/2의 조합을 수가아닌 종류별로 전부 출력되어야 하고 각각에 대해서 점수를 더해야 했다. 점수를 더해야 한다는 조건때문에 조합의 종류를 어떤식으로 출력해야하나 고민이 되기도 했고 무엇보다 조합을 종류별로 찾는게 어려웠다.

예전에 14502번 연구소에서 포스팅 한 내용에서는

for i in range(n):
    for j in range(i+1, n):
        for k in range(j+1, n):

3개라는 조건이 주어졌기에 반복문을 3번 적으면 조합을 쉽게 구할 수 있었지만, 이번 문제에서는 n의 개수에 따라 조합되는 개수가 다르기 때문에 어려움을 겪었다.

좀 오래 생각해본 결과 재귀함수가 반복문 대체가 가능하며 깊이를 지정해주면 될까하는 가능성이 보였고 시도해봤더니 바로 성공했다.

또한, 조합의 결과를 처음에는 [1,2,3,4] 이런식으로 출력할 생각이었으나 link팀도 결정이 되어야 하므로 n+1개의 리스트에서 팀이되면 True, 아니면 False로 조합을 했으며
고등학교때 배운 팀을 나누는 문제는 nCn/2/2 가 되어야 하기에 생각을 살짝 바꿔서 1번과 같은팀과 아닌팀으로 분리해서 n-1C(n/2)-1 을 구한다는 생각으로 코드를 구현하였다.

소스코드

import sys
input = sys.stdin.readline

#짝수
n = int(input())

data = []
for _ in range(n):
    data.append(list(map(int,input().split())))
    
result = int(10e9)

#1번 플레이어는 무조건 start팀
#n-1명중에 start에 n/2 -1명 추가되고 
#link에는 start에 사람이 가면 False처리
start = [False] * (n+1)
link = [True] * (n+1)
start[1] = True
link[0] = link[1] = False

def dfs(deep,start,link,index):
    global result
    
    #이미 결과가 0이면 계산 안함
    if result == 0:
        return
    
    if deep == n//2:
        #스타트 팀과 링크팀의 합계
        start_value = 0
        link_value = 0
        #1~n까지 돌면서 팀에따라 점수배분
        for i in range(1,n+1):
            for j in range(1,n+1):
                if start[i] == True and start[j] == True:
                	#start와link에는 1부터 판단했고 data에는 0부터 저장되있으므로
                    #i와 j에 -1씩 해줌
                    start_value += data[i-1][j-1]
                if link[i] == True and link[j] == True:
                    link_value += data[i-1][j-1]
                    
        #최소 비교
        if start_value >= link_value:
            result = min(result, start_value - link_value)
        else:
            result = min(result, link_value - start_value)
        return
    
    
    for i in range(index,n+1):
        start[i] = True
        link[i] = False
        dfs(deep+1,start,link,i+1)
        start[i] = False
        link[i] = True
        
    
dfs(1,start,link,2)  
    
print(result)