[백준] 14889 스타트와 링크

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

 

14889번: 스타트와 링크

1.조합함수를 사용하기 위한 itertools 모듈 생성

2.짝수의 수 N과 N회 반복하여 길이가 N인 리스트를 리스트 e에 저장해 2차원 리스트 생성

3. 1~N까지 수를 possible_team리스트에 저장

4.start_team = possible_team의 절반(0번째 인덱스~ 절반 인덱스)

  link_team = possible_team의 절반(절반 인덱스~ 마지막 인덱스)

5. start_team 과 link_team 내에서 2명씩 조합하기 >> 점수를 계산하기 위해

 여기서 문제를 잘목 이해해서 시간이 걸렸었다. 만약 N = 6 일 때 start_team = (1,2,3) , link_team = (4,5,6)이면

(1,2)(1,3)(2,3) // (4,5),(4,6)(5,6)일때 점수를 모두 각각 구해 더해야 하는데 이 더하지 않고 바로 차이를 구했기 때문이다.

6.각 팀의 점수를 총 합해 빼고 절댓값 계산

7. 최솟값 구하기

from itertools import combinations  # 조합함수

N = int(input())  # 짝수

e = [list(map(int,input().split())) for _ in range(N)]  # 능력치 입력받기


member = [i+1 for i in range(N)]

possible_team = []
for team in list(combinations(member, N //2)):
    possible_team.append(team)


start_team = []

for i in range(0,len(possible_team)//2):
    start_team.append(possible_team[i])


link_team = []
for i  in range(len(possible_team)-1,len(possible_team)//2-1,-1):
    link_team.append(possible_team[i])




# 팀 내에서 두명씩 조합 만들기
semi_start_team = []
semi_link_team = []

for i in range(len(possible_team)//2):
    semi_start_team.append( list(combinations(start_team[i],2)))
    semi_link_team.append( list(combinations(link_team[i],2)))




final_a_score=[]
final_b_score=[]
for i in range(len(start_team)):
    a_score = []
    b_score = []
    scorea=0
    scoreb=0
    for j in range(len(semi_start_team[i])):
        a = semi_start_team[i][j][0]
        b = semi_start_team[i][j][1]
        scorea += e[a-1][b-1]+e[b-1][a-1]
        c = semi_link_team[i][j][0]
        d = semi_link_team[i][j][1]
        scoreb += e[c-1][d-1]+e[d-1][c-1]
    a_score.append(scorea)
    b_score.append(scoreb)
    final_a_score.append(a_score)
    final_b_score.append(b_score)



sscore = []
for i in range(len(possible_team)//2):
    g = abs(final_a_score[i][0] - final_b_score[i][0])
    sscore.append(g)

print(min(sscore))