boj14889-스타트와 링크

문제 :

스타트와 링크

코드 (시간초과)

나올 수 있는 모든 팀의 조합을 구함 -> 팀별 경험치 합 구해서 그 차이 갱신
--> 시간초과

import sys
from itertools import combinations

if __name__ == '__main__':
    input = sys.stdin.readline

    N = int(input())
    idx = [i for i in range(N)]
    s = []
    for i in range(N):
        input_ = list(map(int, input().split()))
        s.append(input_)

    team_com = list(combinations(idx , N// 2))
    team1 = team_com[:len(team_com)//2]
    team2 = list(reversed([t for t in team_com if t not in team1]))
    # print(team1, team2)

    # 모든 조합의 경험치 차이 계산 
    min_v = 1000
    for t1, t2 in zip(team1, team2):
        exp_com1 = list(combinations(t1, 2))
        exp_com2 = list(combinations(t2, 2))
        # print(exp_com1, exp_com2)
        exp1, exp2 = 0,0
        for (a, b), (c, d) in zip(exp_com1, exp_com2):
            exp1 += s[a][b] + s[b][a]
            exp2 += s[c][d] + s[d][c]
        if abs(exp1 - exp2) < min_v:
            min_v = abs(exp1 - exp2)  
    # print(f'min_V : {min_v}' )
    print(min_v)

설명

중간에 team2 구하는거 그냥 뒤에거 반 하면 맞음,,, 왜 저렇게 풀었지?

team_com = list(combinations(idx , N// 2))
team1 = team_com[:len(team_com)//2]
team2 = team_com[len(team_com)//2:]
team2.reverse()

코드 (2756ms)

import sys
input = sys.stdin.readline
from itertools import combinations

n = int(input())
team=[i for i in range(n)]
g = [list(map(int, input().split())) for _ in range(n)]
comb = list(combinations(team, n//2))
# print(comb)
tot1 ,tot2 = [], []
for i in range(len(comb)//2):
    t = 0
    for x,y in combinations(comb[i], 2):
        t += g[x][y] + g[y][x]
    tot1.append(t)
for i in range(len(comb)//2, len(comb)):
    t = 0
    for x,y in combinations(comb[i], 2):
        t += g[x][y] + g[y][x]
    tot2.append(t)
tot2.reverse()
# print(tot1,tot2)
answer = 201
for t1,t2 in zip(tot1, tot2):
    answer = min(answer, abs(t1-t2))
print(answer)

설명

combination을 이용하여 나올수 있는 모든 팀의 조합 구함
해당 조합에서 다시 팀별 경험치를 더해서 저장 - 차이가 제일 작은 값 출력