용답노트

오답노트

• / 연산자는 소수점에서 오류를 일으킬 수 있어서 // 연산자가 안전하다.
• == 과 = 실수하지 않도록 주의.

궁금한 내용

• 아래 코드에서 diff 는 global 선언을 해야하고, maps/visited/n 등은 global 선언을 하지 않아도 되는 이유는?
• 1,2,3,4 가 있는 상황에서 1,2 가 start팀이 되는 경우와 3, 4가 start팀이 되는 경우의 팀 능력치 차이가 동일한데, 한번만 계산하는 방법은 없을까?
• 글이 한차례 날아갔음... 알고리즘 적으로 궁금한 내용이 한가지 더 있었으나 기억이 안남..

흐름

• n 명 중에 2/n 명을 뽑는다. (백트래킹, 뽑힌 인원은 visited 에서 1, 뽑히지 않으면 visited 0)
• dfs의 depth가 2/n이 되면 start 팀과 link팀에 점수를 계산하고, 현재 최소값과 비교한다.

코드

n = int(input())

visited = [False for _ in range(n)]
maps = [list(map(int, input().split())) for _ in range(n)]
diff =int(1e9)

def dfs(x,depth):
    global diff
    if depth == n//2:
        start = 0
        link = 0 
        for i in range(n):
            for j in range(i+1, n):
                if visited[i] == 1 and visited[j] == 1:
                    start += (maps[i][j] +  maps[j][i] )
                elif visited[i] == 0 and visited[j] ==0 :
                    link += (maps[i][j] +  maps[j][i])
        diff = min(abs(start-link),diff)
        return
    
    for i in range(x, n):
        if visited[i] == False:
            visited[i] = True
            dfs(i+1,depth+1)
            visited[i] = False

dfs(0,0)
print(diff)