백준 - 스타트와 링크(14889)

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

삼성 역량테스트 - Brute Force

from itertools import combinations
from itertools import permutations

n = int(input())
li = [(i + 1) for i in range(n)]
half = int(len(li) / 2)
N = list(combinations(li, half))
length = len(N)
result = []
s = [list(map(int, input().split())) for _ in range(n)]

for i in range(len(N)):
    a = N[i]
    b = N[length - 1 - i]
    aPer = list(permutations(a, 2))
    bPer = list(permutations(b, 2))
    aSum = 0
    bSum = 0
        
    for j in range(len(aPer)):
        aSum += (s[aPer[j][0] - 1][aPer[j][1] - 1])
        bSum += (s[bPer[j][0] - 1][bPer[j][1] - 1])
            
    result.append(abs(aSum - bSum))
        
print(min(result))

시간 초과

from itertools import combinations

n = int(input())
members = [i for i in range(n)] # 가능한 팀 조합을 만들기 위한 재료
s = [list(map(int, input().split())) for _ in range(n)]
possibleTeam = list(combinations(members, n // 2)) # 전체 인원을 두 그룹으로 나눈 조합 배열
gap = 10000 # 최솟값을 갱신할 초기 gap

for i in range(len(possibleTeam) // 2):
    team = possibleTeam[i] 
    A = 0 # 누적할 스텟값
    for j in range(n // 2):
        member = team[j] # 해당 조합 팀의 각 선수 설정
        for k in team: # 선수와 다른 선수 조합의 스탯 조회, 자기 자신과 스탯은 0
            A += s[member][k] # 스탯누적
    
    opposite = possibleTeam[-i-1] # 상대팀 마찬가지로 진행
    B = 0
    for j in range(n // 2):
        oppositeMember = opposite[j]
        for k in opposite:
            B += s[oppositeMember][k]
            
    gap = min(gap, abs(A - B)) # gap을 스탯값 차이와 비교
    
print(gap)

길이가 n인 팀 조합 배열에서 인덱스 기준 (0, n - 1), (1, n - 2) ... 식으로 경기하면 딱 맞게 떨어진다. 그래서 총 인원이 짝수로 주어진 것.

참고)
https://www.acmicpc.net/problem/14889