백준 14889번 - 스타트와 링크 [Python]

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

14889번: 스타트와 링크

문제

오늘은 스타트링크에 다니는 사람들이 모여서 축구를 해보려고 한다. 축구는 평일 오후에 하고 의무 참석도 아니다. 축구를 하기 위해 모인 사람은 총 N명이고 신기하게도 N은 짝수이다. 이제 N/2명으로 이루어진 스타트 팀과 링크 팀으로 사람들을 나눠야 한다.

BOJ를 운영하는 회사 답게 사람에게 번호를 1부터 N까지로 배정했고, 아래와 같은 능력치를 조사했다. 능력치 Sij는 i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치이다. 팀의 능력치는 팀에 속한 모든 쌍의 능력치 Sij의 합이다. Sij는 Sji와 다를 수도 있으며, i번 사람과 j번 사람이 같은 팀에 속했을 때, 팀에 더해지는 능력치는 Sij와 Sji이다.

N=4이고, S가 아래와 같은 경우를 살펴보자.

	1	2	3	4
1		1	2	3
2	4		5	6
3	7	1		2
4	3	4	5

예를 들어, 1, 2번이 스타트 팀, 3, 4번이 링크 팀에 속한 경우에 두 팀의 능력치는 아래와 같다.

• 스타트 팀: S12 + S21 = 1 + 4 = 5
• 링크 팀: S34 + S43 = 2 + 5 = 7

1, 3번이 스타트 팀, 2, 4번이 링크 팀에 속하면, 두 팀의 능력치는 아래와 같다.

• 스타트 팀: S13 + S31 = 2 + 7 = 9
• 링크 팀: S24 + S42 = 6 + 4 = 10

축구를 재미있게 하기 위해서 스타트 팀의 능력치와 링크 팀의 능력치의 차이를 최소로 하려고 한다. 위의 예제와 같은 경우에는 1, 4번이 스타트 팀, 2, 3번 팀이 링크 팀에 속하면 스타트 팀의 능력치는 6, 링크 팀의 능력치는 6이 되어서 차이가 0이 되고 이 값이 최소이다.

문제 유형 / 난이도

완전탐색 / 실버 2

문제 풀이

우선 시간 제한이 2초이고 N은 최대 20까지이다. 또한 (i,j)와 (j,i)를 합한다고 했으므로 i와 j는 순서에 상관없이 팀을 이룬다. 따라서 20명중 반절을 팀으로 구성하는 경우의 수는 20C10 = (20 x 19 x ... x 11) / 10! = 대략 20만 정도가 된다. 1초에 2000만의 연산을 수행한다고 할때 4000만 정도의 연산을 허용하고 한번의 팀을 구성할 때마다 모든 (i,j)와 (j,i)를 찾아야하니 2중 루프가 필요하다. 따라서 N^2의 시간 복잡도를 갖기 때문에 20만 * 400은 8000만이므로 오버헤드와 기타 연산들까지 모두 합치면 1억 번 이상의 연산이 수행된다고 생각할 수 있다. 따라서 python으로는 시간초과가 날 것이기 때문에 pypy로 돌리거나 자바로 전환하자.

 

N명에서 반절이 팀을 이루는 모든 경우의 수를 구하고 해당 인원의 (i,j)와 (j,i)를 모두 합한 값과 한팀의 인원이 되고 반대편 팀의 (i,j)와 (j,i)를 모두 합한 값의 차가 최솟값이 값을 구한다.

python

import sys
input = sys.stdin.readline


def bt(cnt, idx):
    global gap
    if cnt == n//2:
        start, link = 0, 0
        for i in range(n):
            for j in range(n):
                if visited[i] and visited[j]:
                    start += graph[i][j]
                elif not visited[i] and not visited[j]:
                    link += graph[i][j]
        gap = min(gap, abs(start-link))
        return
    
    for i in range(idx, n):
        if not visited[i]:
            visited[i] = True
            bt(cnt+1, i+1)
            visited[i] = False
                    
        
n = int(input())
graph = [list(map(int, input().split())) for _ in range(n)]
visited = [False]*n
gap = int(1e9)
bt(0,0)

print(gap)

feedback

파이썬으로 풀기에는 아슬아슬한 문제이다. 시간복잡도가 많이 나올것 같은 문제는 자바로 풀도록 하자.