백준, 스타트와 링크, 14889

[유형]

백트래킹, 조합

 

[문제링크]

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

 

[요약]

축구를 하기 위해 모인 사람은 총 N명이고 신기하게도 N은 짝수이다. 이제 N/2명으로 이루어진 스타트 팀과 링크 팀으로 사람들을 나눠야 한다.

능력치 Sij는 i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치이다. 팀의 능력치는 팀에 속한 모든 쌍의 능력치 Sij의 합이다. Sij는 Sji와 다를 수도 있으며, i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치는 Sij와 Sji이다.

첫째 줄에 스타트 팀과 링크 팀의 능력치의 차이의 최솟값을 출력한다.

 

[문제풀이]

가장 먼저 조합을 사용해서 문제를 해결할 수 있다. 

import sys
from itertools import combinations

def input():
    return sys.stdin.readline().rstrip()

def team():
    global result
    for start_member in list(combinations(S_idx, N//2)):
        start_total = link_total = 0

        link_member = list(set(S_idx)-set(start_member))

        for i, j in list(combinations(start_member, 2)):
            start_total += S[i][j]
            start_total += S[j][i]

        for i, j in list(combinations(link_member, 2)):
            link_total += S[i][j]
            link_total += S[j][i]

        result = min(result, abs(start_total - link_total))



N = int(input())
S = [list(map(int, input().split())) for _ in range(N)]
S_idx = list(range(N))
result = float('inf')
team()
print(result)

 

두번째 방법으로는 백트래킹을 사용할 수 있는데, 시간은 조합을 사용했을 떄보다 두배 더 오래 걸린다.

N자리의 모든 갯수를 탐색하는 것이 아니라, 절반만 탐색한다. (for x in range(n,N))

방문 여부를 체크해서, 방문한 절반을 같은 팀, 방문하지 않은 절반을 같은 팀으로 만들어준다.

 

import sys

def input():
    return sys.stdin.readline().rstrip()
def team(a,n):
    global result
    if a == N//2:
        start, link = 0, 0
        for i in range(N):
            for j in range(N):
                if visited[i] and visited[j]:
                    start += S[i][j]
                elif not visited[i] and not visited[j]:
                    link += S[i][j]
        result = min(result, abs(start-link))
        return

    else :
        for x in range(n,N):
            if visited[x] == 0:
                visited[x] = 1
                team(a+1,x+1)
                visited[x] = 0


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

visited = [0]*N
result = float('inf')
team(0,0)
print(result)