14889번 - 스타트와 링크

문제

 

14889번: 스타트와 링크 (acmicpc.net)

14889번: 스타트와 링크

풀이 1

itertools 모듈을 쓰지 않고 푸는데 의의가 있는 문제이다. 모든 선수들은 두 그룹으로 나뉘는데, 첫번째 선수를 포함한 그룹과 그렇지않은 그룹이다. 선수를 n/2 만큼 모으면, get_point 메서드를 통해 점수를 계산하고 두 팀의 점수차를 구한다.

import sys
input = sys.stdin.readline
n = int(input())
s = []
for _ in range(n):
    s.append(list(map(int, input().split())))
answer = int(1e9)
total = set(range(n))


def get_point(team):
    team = list(team)
    result = 0
    for i in range(n//2 - 1):
        for j in range(i+1,n//2):
            result += s[team[i]][team[j]] + s[team[j]][team[i]]
    return result


def dfs(i,cnt,team):
    global answer
    if cnt == n//2:
        # print(f'{team}:{get_point(team)} {total - team}:{get_point(total-team)}')
        answer = min(answer,abs(get_point(team)-get_point(total-team)))
        return
    for j in range(i+1,n):
        dfs(j,cnt+1,team | set([j]))

dfs(0,1,set([0]))
print(answer)

풀이 2

두 팀은 서로 구분되지 않는다. 예를 들어 선수가 [1, 2, 3, 4] 가 있다고 했을 때, [1, 2], [3, 4] 로 나누나 [3, 4], [1, 2]로 나누나 같은 경우라는 것이다. 1을 포함한 팀과 그렇지 않은 팀으로 나누면 된다.

N = int(input())
S = [[0]*(N+1)]
for _ in range(N):
    S.append([0] + list(map(int,input().split())))
players = set(range(1,N+1))
# 1을 반드시 포함하는 팀
team = []
team.append(1)


def get_point(li):
    result = 0
    for i in range(N//2):
        for j in range(i+1,N//2):
            result += S[li[i]][li[j]]+S[li[j]][li[i]]
    return result


def dfs(cnt,start):
    global answer
    if cnt == N//2:
        a,b = get_point(team),get_point(list(players - set(team)))
        answer = min(answer,abs(a-b))
        return

    for i in range(start,N+1):
        team.append(i)
        dfs(cnt+1,i+1)
        team.pop()


answer = int(1e9)
dfs(1,2)
print(answer)