[Algorithm] 1일1솔 - 백준 14889 스타트와 링크 (python3)

문제링크

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

14889번: 스타트와 링크

 

문제설명

짝수 N명의 사람들을 스타트 팀과 링크 팀으로 나누었을 때, 팀 간 능력치를 최소화하는 문제이다.

S는 팀의 i번 사람과 j번 사람이 같은 팀에 속했을 때의 능력치를 담은 2차원 배열이며, S_ij 와 S_ji 는 다르게 취급되므로 그 경우를 각각 따져주기 위해 이중 for 문으로 각 능력치를 구하여 팀 전체의 능력치에 더해줬다.

문제풀이

combinations 를 활용해서 팀 조합을 만들고, 스타트팀과 링크팀의 능력치를 각각 구한 다음 능력치의 최솟값을 갱신하며 구했다. 링크팀은 팀 조합 중, 스타트팀으로 쓰인 팀과 겹치지 않도록 팀 조합의 맨 뒤 경우부터 따져주었다. (스타트팀은 팀 조합의 맨 앞부터 차례로)

i번 사람과 j번 사람에 대한 능력치를 구하는 것이므로 S의 행과 열이 같은 경우는 if 문으로 제외해주었으나, 실질적으로 채점해보았을 때는 if 문을 넣어주지 않았을 경우가 더 빨랐다. (약 570ms 차이)

이미 col을 구하기 위한 for 문을 돌고 if 문을 처리해줘서 오히려 느려지는 것 같고, 어차피 행과 열이 같을 때의 능력치가 이미 0으로 들어와있기 때문에 그냥 다 더해줘도 처리속도에 있어서 문제가 있지 않은 것 같다.

import sys
from itertools import combinations
input = sys.stdin.readline
n = int(input())
s = [list(map(int, input().split())) for _ in range(n)]
members = [i for i in range(n)]
team_comb = list(combinations(members, n//2))
min_gap = sys.maxsize

for i in range(len(team_comb)//2):	# 스타트팀과 링크팀의 두 경우를 따지기 위해 팀 조합의 반까지의 인덱스를 돌게 했다.
# 스타트팀
    team = team_comb[i]	# 팀 조합의 인덱스 0 ~ len(team_comb)//2 -1 까지
    start = 0
    for j in range(n//2):	# 팀 인원(n//2) 중에서  
        row = team[j]
        for col in team:
            if col != row:	# if 구간을 없애주는 것이 속도가 더 빠름
                start += s[row][col]

# 링크팀
    team = team_comb[-i-1]	# 팀 조합의 인덱스 -1(= len(team_comb)-1) ~ len(team_comb)//2 (= -len(team_comb)//2) 까지 역순으로
    link = 0
    for j in range(n//2):	# 팀 인원(n//2) 중에서 
        row = team[j]
        for col in team:
            if col != row:  # if 구간을 없애주는 것이 속도가 더 빠름
                link += s[row][col]
    min_gap = min(min_gap, abs(start-link))
print(min_gap)