백준 14889번: 스타트와 링크 (Python)

접근

각 팀에 N/2명씩 나누었을 때 사람들 끼리 가지는 시너지를 계산하여 팀 사이의 능력치 차이가 가장 적도록 하는 문제이다. 예를 들어 1번 선수와 4번 선수가 같은 팀일 경우 table[1][4] 와 table[4][1]을 팀 능력치에 더해주면 된다.

처음에는 각 팀에 선수 한명씩을 배정해주고, 새로운 팀원이 들어올 때마다 기존 팀을 순환하면서 table[i][j]와 table[j][i]를 더해주는 방식으로 코드를 짰는데 시간도 오래걸릴 뿐더러 중복되는 경우를 구분하기 어려웠다. 따라서 방법을 바꾸어 첫번째 선수(아래 코드에서는 0번 선수)가 포함되는 N/2명의 선수 명단을 모두 구하고(0번 선수가 두번째 팀에 가서 순환해도 모두 기존 구한 팀 명단과 중복된다.), 각 경우에 팀이 가지는 능력치를 계산하여 그 차이를 저장해주었다.

코드

import sys


n = int(sys.stdin.readline())
table = []
for i in range(n):
    m = list(map(int, sys.stdin.readline().split()))
    table.append(m)
team_pool = set(range(1, n))
pool_used = [False] * n
pool_used[0] = True
team_start = [0]
team_start_possible = []  # 스타트 팀 명단이 될 수 있는 집합들의 리스트
ans = []
score = [0, 0]


def team_making(x):  # 0번 선수가 포함된 팀에 N/2명의 선수가 채워질 때마다 이를 team_start_possible에 저장한다.
    if len(team_start) == n // 2:
        team_start_possible.append(set(team_start))
        return
    for j in range(x + 1, n):
        if pool_used[j] is True:
            continue
        team_start.append(j)
        pool_used[j] = True
        team_making(j)
        pool_used[j] = False
        team_start.pop()


team_making(0)
for k in range(len(team_start_possible)):
    team_link = team_pool - team_start_possible[k]  # 전체 선수에서 스타트 팀을 빼면 링크 팀이 구해진다.
    team_start_list = list(team_start_possible[k])
    team_link_list = list(team_link)
    for x in range(n // 2):  # 각 팀을 돌면서 선수들끼리 서로의 시너지를 구하되 중복을 고려하여 2로 나누어준다.
        for y in range(n // 2):
            score[0] += table[team_start_list[x]][team_start_list[y]] + table[team_start_list[y]][team_start_list[x]]
            score[1] += table[team_link_list[x]][team_link_list[y]] + table[team_link_list[y]][team_link_list[x]]
    ans.append(abs(score[0] - score[1]) // 2)
    score = [0, 0]
print(min(ans))

이전에 풀었던 문제를 다시한번 풀어보았고, 시간이 많이 개선되어 코드를 첨부합니다.

이번에는 dfs 를 이용하여 각 번호의 멤버에 대해 양쪽의 팀에 배정하고, 배정이 완료되면 양팀의 점수차의 최소값을 갱신하도록 합니다.

이번에도 첫번째 멤버가 1번째 팀에만 있도록 하여 중복 계산을 생략하였습니다.

N = int(input())
S = [list(map(int, input().split(" "))) for _ in range(N)]
visited = [0] * N
result = float("inf")


def getTeamScore(arr):
    teamScore = 0
    for i in range(N // 2 - 1):
        for j in range(i + 1, N // 2):
            teamScore += S[arr[i]][arr[j]] + S[arr[j]][arr[i]]
    return teamScore


def getTeam(depth, i, aTeam, bTeam):
    global result
    if depth == N:
        result = min(result, abs(getTeamScore(aTeam) - getTeamScore(bTeam)))
    if len(aTeam) < N // 2:
        getTeam(depth + 1, i + 1, aTeam + [i], bTeam)
    if len(bTeam) < N // 2:
        getTeam(depth + 1, i + 1, aTeam, bTeam + [i])


getTeam(1, 1, [0], [])
print(result)

더 생각해 볼 것?

team_making 함수가 곰곰이 생각해보니, 수학에서 조합과 비슷하다는 생각이 들었다. 아니나 다를까 찾아봤더니 python에는 itertools가 있어서 permutation(순열)과 combination(조합)을 구할 수 있었다..!

from itertools import permutations, combinations

combinations 함수를 이용하여 더 간단한 코드로 작성해 보면 좋을 것 같다.