스타트와 링크 링크와 스타트

#14889번 스타트와 링크 https://www.acmicpc.net/problem/14889

14889번: 스타트와 링크

import sys
N = int(input())
matrix = []

for i in range(N):
    matrix.append(list(map(int, sys.stdin.readline().split())))


def get_sum(team):
    parts = 0
    for i in range(len(team)):
        for j in range(i+1, len(team)):
            parts += (matrix[team[i]][team[j]] + matrix[team[j]][team[i]])
    return parts


members = []
answer = 100


def solve(depth, prev):
    global answer
    if depth == N//2:
        second_team = [x for x in range(N) if x not in members]
        tmp = abs(get_sum(members) - get_sum(second_team))
        answer = min(answer, tmp)
        return

    for i in range(prev, N):
        members.append(i)
        solve(depth+1, i+1)
        members.pop()


solve(0, 0)
print(answer)

뭐 재귀를 통해 무난하게 해결

 

다음에 바로 유사한 문제를 만났다.

 

#15661번 링크와 스타트https://www.acmicpc.net/problem/15661

15661번: 링크와 스타트

차이점은 인원수가 동일하지 않을 때도 계산해야한다는 점.

 

나는 기존의 코드를 재사용하려고 했다.

import sys
N = int(input())
matrix = []

for i in range(N):
    matrix.append(list(map(int, sys.stdin.readline().split())))


def get_sum(team):
    parts = 0
    for i in range(len(team)):
        for j in range(i+1, len(team)):
            parts += (matrix[team[i]][team[j]] + matrix[team[j]][team[i]])
    return parts


visited = [False]*N
answer = 1000


def solve(depth, prev, stop):
    global answer
    if depth == stop:
        members, second_team = [], []
        for i in range(N):
            if visited[i]:
                members.append(i)
            else:
                second_team.append(i)
        if len(members) * len(second_team) == 0:
            return
        answer = min(answer, abs(get_sum(members) - get_sum(second_team)))
        return

    for i in range(prev, N):
        visited[i] = True
        solve(depth+1, i+1, stop)
        visited[i] = False


for i in range(1, N//2+1):
    solve(0, 0, i)

print(answer)

기존의 종료조건을 1~절반까지 가변하는 방식으로 구현했다.

 

그런데 결과는 시간초과. 결국 pypy3로 통과했다.

 

아예 다른 방법이 필요하다.

 

import sys
from itertools import combinations

input = sys.stdin.readline

n = int(input())

matrix = [list(map(int,input().split())) for _ in range(n)]

d = 20*100
for i in combinations(range(n),n//2):

    s_team = [*i]
    l_team = list(set(range(n)) - set(s_team))

    s_score = 0
    l_score = 0
    for j in combinations(s_team,2):
        s_score += matrix[j[0]][j[1]] + matrix[j[1]][j[0]]
    
    for j in combinations(l_team,2):
        l_score += matrix[j[0]][j[1]] + matrix[j[1]][j[0]]
    
    sub = abs(s_score - l_score)

    if sub == 0:
        d = sub
        break

    elif d > sub:
        d = sub

print(d)

근데 뭐 역시나 itertools 라이브러리를 사용한 방법밖에 찾지 못했다.

 

파이썬을 파이썬답게 쓰는 방법은 라이브러리를 꼭 사용해야하는걸까?

뭐 앞으로 코딩테스트를 진행할 언어를 바꿀 생각은 없지만

파이썬은 항상 기본 라이브러리를 활용할 때 가장 빠른걸까

 

여러 의문의 드는 하루였다.