[백준 14889] 스타트와 링크

[BanApp]

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

pypy3

import sys
from itertools import combinations
n = int(sys.stdin.readline())

arr = []
arr.append(['x' for _ in range(n+1)])
for i in range(n):
    arr.append(['x',*list(map(int,sys.stdin.readline().split()))])

member = []
for i in range(1,n+1):
    member.append(i)

team = list(combinations(member,n//2))
mi = float('inf')
for i in range(len(team)//2):
    team1 = team[i]
    team2 = team[len(team)-i-1]
    p_team1 = list(combinations(team1,2))
    p_team2 = list(combinations(team2,2))

    a_team1 = 0
    a_team2 = 0
    for j in range(len(p_team1)):
        a_team1 = a_team1 + arr[p_team1[j][0]][p_team1[j][1]] + arr[p_team1[j][1]][p_team1[j][0]]
        a_team2 = a_team2 + arr[p_team2[j][0]][p_team2[j][1]] + arr[p_team2[j][1]][p_team2[j][0]]

    if abs(a_team1 - a_team2) < mi:
        mi = abs(a_team1 - a_team2)

print(mi)

아니 이거 백트래킹에 들어가 있어서 백트래킹으로 풀어보려고 번호 깔끔하게 맞출생각에 앞에 x로 감싸 줬는데 결국 조합으로 풀었다.
만약에 내가 시험장에서 저 문제를 만났다면 똑같이 이렇게 풀었을거다.
근데 이걸 백트래킹으로 풀 수 있다고? 이게 백트래킹으로만 풀렸으면 과연 실버에 있을 문제인가?
내가 구현한 아이디어는 일단 반으로 팀을 쪼갤 수 있는 조합을 모두 만든다. 늘 그렇듯 python은 combinations 함수가 있다.
해당 조합은 0번째에 대응 되는 조합이 예를 들어 0번이 (1,2,3) 이면 n-1번째에 (4,5,6) 이렇게 나온다.
이렇게 만든 team1, team2 조합은 팀원들을 구성할 수 있는 조합이고 능력치 비교를 위해서는 안에 있는 선수들을 2명씩 또 조합을 이용해서 뽑아 줘야 한다. 능력치 비교를 위해서 최종적으로 만든 리스트가 p_team1 이다. 이제 이를 대각선 으로 더해주면서 최종적으로 모든 조합을 다 더해주면 a_team1 과 a_team2에 각 선수들의 능력치 합이 담기게 된다. 아까 말한 것처럼 team 리스트도 (0,n-1),(1,n-2) 이런식으로 대응 하기 때문에 n//2 번 만큼 반복하면서 기존 능력치 차이값보다 작은지 비교해주고 반복문이 끝난 다음에 남은 mi값이 능력치 차이가 가장 적은 것이므로 출력해준다 끝!

[ghdcksgml1]

ㅋㅋㅋㅋ 백트래킹으로 조합을 구현할 수 있어서 그런게에용. 푸신방법이 맞습니다.