백준 14889번_스타트와 링크 [python/파이썬]

 

num_player = int(input())
player_list = [i for i in range(num_player)]
player_ability_list = []
for player in range(num_player):
    player_ability_list.append(list(map(int, input().split())))
 
check_list=[False]*num_player
output=[]
diff = 1000000
 
def diff_set(player_list, team1): # 차집합 구하기
    result = player_list[:]
    for i in player_list:
        for j in team1:
            if i == j:
                result.remove(i)
    return result
 
def ability_check(player_ability_list, num_list):
    total_ability = 0
    for i in num_list:
        for j in num_list:
            total_ability += player_ability_list[i][j]
    return total_ability
 
def combination(count): # 조합 구하기
    global diff
    if count == num_player//2:
        team1 = output
        team2 = diff_set(player_list, team1)
        team1_ability = ability_check(player_ability_list, team1)
        team2_ability = ability_check(player_ability_list, team2)
        diff = min(diff, abs(team1_ability - team2_ability))
        return
 
    for i in range(num_player):
        if check_list[i] == True:
            continue
 
        check_list[i] = True
        output.append(i)
        combination(count+1)
        output.pop()
        for j in range(i+1,num_player):
            check_list[j] = False
 
combination(0)
print(diff)
 

 

 itertools의 combination을 사용하지 않고 직접 코드를 작성해 사용하였다.