[백준][파이썬] 14889 스타트와 링크

# 팀을 나눈다 n/2명씩
# 1. 재귀 함수를 통해서 팀 조합 생성
# 2. 능력치를 더해주는 함수를 통해서 능력치 생성
# 3. 비교 및 최소값 구하기
import sys

num = int(sys.stdin.readline())
power = [list(map(int, input().split())) for _ in range(num)]

p = int(num/2) #팀원 수
check = [False] * num
mn = 10**9

def sum_power(s):
    t1 = 0
    t2 = 0
    for i in range(num):
        for j in range(i,num):
            if i != j and s[i] == s[j] and s[i] == True:
                t1 += power[i][j]
                t1 += power[j][i]
            elif i != j and s[i] == s[j] and s[i]== False:
                t2 += power[i][j]
                t2 += power[j][i]
    total = abs(t1- t2)
    return total



def recu(cnt, s):
    global mn
    if len(s) == p:
        ans = sum_power(check)
        if mn > ans:
            mn = ans

    for i in range(cnt,num):
        if check[i] == False:
            check[i] = True
            recu(cnt+1, s+str(i))
            check[i] = False
    return

recu(0,"")
print(mn)

-> 시간 제한

 

itertools를 사용한 풀이, 하지만 itertools을 통한 조합은 코테에서 제한

from itertools import combinations #조합 함수

N = int(input())
S = [list(map(int, input().split())) for _ in range(N)]
members = [i for i in range(N)]
possible_team = []

#조합으로 가능한 팀 생성해주기
for team in list(combinations(members, N//2)):
    possible_team.append(team)

min_stat_gap = 10000 #갭이 가장 작은 값을 찾기 위하여
for i in range(len(possible_team)//2):
    #A 팀
    team = possible_team[i]
    stat_A = 0 #A팀 능력치
    for j in range(N//2):
        member = team[j] #멤버
        for k in team:
            stat_A += S[member][k] #멤버와 함께할 경우의 능력치들
            
    #A를 제외한 나머지 팀
    team = possible_team[-i-1]
    stat_B = 0
    for j in range(N//2):
        member = team[j]
        for k in team:
            stat_B += S[member][k]
            
    min_stat_gap = min(min_stat_gap, abs(stat_A - stat_B))
    
print(min_stat_gap)

claude-u.tistory.com/372

#321 백준 파이썬 [14889] 스타트와 링크