(python) 14889 스타트와 링크

백트래킹 문제

백트래킹으로 경우의 수를 뽑아 정답을 찾아내는 문제다.

 

python의 경우 combination 함수를 제공해주기 때문에 편리하게 구현할 수 있다.

 

 

알고리즘

 

1. combination으로 팀을 나눈다.  - 뽑아진 인덱스를 전부 탐색하면 중복 탐색이 되기 때문에 절반만 사용한다.

 

2. 뽑힌 인덱스, 안뽑힌 인덱스끼리 팀을 맻는다.

 

3. 각 팀별 2개의 조합을 뽑아준다. [1,2,3]일 경우 [1,2],[1,3],[2,3]

 

4. reduce함수를 이용해 능력치 합을 구한다.

 

5. 각 팀별 능력치 합의 차이를 결과에 append 한다.

 

6. 결과의 최소값 출력

import itertools
import sys
from functools import reduce
input = sys.stdin.readline

N = int(input())
li = [list(map(int, input().rstrip().split())) for _ in range(N)]

team = list(itertools.combinations(range(N),(N//2)))
team = team[:int(len(team)/2)]
result = []

def teamStateSum(teamindex):
    x = teamindex[0]
    y = teamindex[1]
    return li[x][y] + li[y][x]

def teamReduce(teamCombi):
    result = (reduce(
        lambda x, y : (x + y), (teamStateSum(i) for i in teamCombi)
    ))
    return result

def teamCombiList(t):
    r = teamReduce(list(itertools.combinations(t, 2)))
    return r

for i in team:
    teamB = [j for j in range(N)]
    for j in i:
        teamB.remove(j)

    result.append(abs(teamCombiList(i) - teamCombiList(teamB)))

print(min(result))