백준 - 14889번: 스타트와 링크 파이썬

www.acmicpc.net/problem/14889

14889번: 스타트와 링크

 

난이도 실버3:

직전에 올렸던 permutation과 combination을 구현해서 작성한 코드이다.

 

실질적으로는 combination만 사용하였다.

def permutation(arr, r):

    used = [0]*len(arr)
    per2return=[]

    def generate(item, used):

        if len(item) == r:
            per2return.append(item.copy())
            return

        # 3.
        for i in range(len(arr)):
            if not used[i]:
                item.append(arr[i])
                used[i] = 1
                generate(item, used)
                used[i] = 0
                item.pop()

    generate([], used)
    return per2return

def combination(arr, r):

    comb_return=[]

    def generate(chosen):
        if len(chosen) == r:
            comb_return.append(chosen.copy())
            return

        start = arr.index(chosen[-1]) + 1 if chosen else 0

        for i in range(start, len(arr)):
            chosen.append(arr[i])
            generate(chosen)
            chosen.pop()

    generate([])
    return comb_return


def getpoint_diff(point, team):
    point1 = 0
    point2 = 0

    point_comb = combination(team, 2)
    for i in point_comb:
        point1 += point[i[0] - 1][i[1] - 1] + point[i[1] - 1][i[0] - 1]

    team2 = []
    for i in range(1, len(team)*2 + 1):
        if i not in team:
            team2.append(i)

    point_comb2 = combination(team2, 2)
    for i in point_comb2:
        point2 += point[i[0] - 1][i[1] - 1] + point[i[1] - 1][i[0] - 1]

    return abs(point1 - point2)


T=int(input())

point=[list(map(int,input().split())) for _ in range(T)]

team1 = combination(range(1,T+1),T/2) #split to team

sum_point=[0]*len(team1)

for i in range(len(team1)):
    sum_point[i]= getpoint_diff(point,team1[i])

print(min(sum_point))

 

python은 통과하지 못했고 pypy3를 사용해 통과하였다.