[백준] 14889 스타트링크

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번이 링크 팀에 속한 경우에 두 팀의 능력치는 아래와 같다.

• 스타트 팀: 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이 되고 이 값이 최소이다.

 

입력

첫째 줄에 N(4 ≤ N ≤ 20, N은 짝수)이 주어진다. 둘째 줄부터 N개의 줄에 S가 주어진다. 각 줄은 N개의 수로 이루어져 있고, i번 줄의 j번째 수는 Sij 이다. Sii는 항상 0이고, 나머지 Sij는 1보다 크거나 같고, 100보다 작거나 같은 정수이다.

 

출력

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

 

 

풀이

N이 최대 20까지 들어오고 항상 N/2만큼의 인원으로 팀을 구성하기 때문에 최대 나올 수 있는 경우의 수는 20C10이다.
여기서 팀 점수를 계산하는 것도 N^2이 아닌 N(N+1)/2로 계산해야 Python으로 채점했을 때 시간안에 정답이 나왔다.

먼저 가능한 모든 조합을 구성해야하는데 itertools의 combination을 사용하면 쉽게만들 수 있지만
모듈을 사용할 수 없는 경우도 있기 때문에 dfs를 이용하여 직접 구현하였다.

 

# level은 선택한 갯수
def dfs(count:int):
    if count == N/2:
        LINK = 0
        START = 0
        for i in range(N):
            if used[i]:
                for j in range(N):
                    if used[j]:
                        START += power[i][j]
            else:
                for j in range(N):
                    if used[j] is False:
                        LINK += power[i][j]
        global answer
        if abs(START - LINK) < answer:
            answer = abs(START - LINK)
# 순열과 동일한 시간이 소요됨
    for now in range(N):
        if used[now] == True:
            continue
        used[now] = True
        dfs(count + 1)
        used[now] = False

dfs의 인자로는 지금까지 선택한 선수의 숫자를 받고 그 수가 N//2가 되면 연산하는 방식으로 구현하였는데
시간초과가 나왔다. 분기 선택을 0부터 돌기때문에 used를 사용해서 체크하지만 순열을 만드는 것과 동일한 시간이 소요된다.

 

def dfs(count:int, idx:int):
	###############################
    #########중간 코드 생략########
    ###############################
    for now in range(idx, N):
        if used[now]:
            continue
        used[now] = True
        dfs(count + 1, now + 1)
        used[now] = False

 

인자로 idx를 받아서 for를 idx부터 돌면 조합을 구하는 시간이 소요되기 때문에 시간이 단축된다.
20^10 => 20C10
하지만 이 경우에도 pypy가 아닌 python으로 측정하면 시간초과가 나왔는데 팀 점수를 연산할 때 N^2의 연산을 수행하기 때문이였다.

 

for i in range(N):
            if used[i]:
                for j in range(i + 1, N):
                    if used[j]:
                        START += power[i][j]
                        START += power[j][i]
            else:
                for j in range(i + 1, N):
                    if used[j] is False:
                        LINK += power[i][j]
                        LINK += power[j][i]

점수를 구할 때도 2번째 반복문의 시작을 1번째 반복문의 인자로 넣어주고 ij, ji를 모두 더하는 방식으로 구현하니 시간 안에 통과할 수 있었다.

 

 

전체 코드

import sys

N = int(sys.stdin.readline().rstrip())
power = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
used = [False for _ in range(N)]
answer = 10000

# level은 선택한 갯수
def dfs(count:int, idx:int):
    if count == N//2:
        LINK = 0
        START = 0
        for i in range(N):
            if used[i]:
                for j in range(i + 1, N):
                    if used[j]:
                        START += power[i][j]
                        START += power[j][i]
            else:
                for j in range(i + 1, N):
                    if used[j] is False:
                        LINK += power[i][j]
                        LINK += power[j][i]
        global answer
        if abs(START - LINK) < answer:
            answer = abs(START - LINK)
            if answer == 0:
                print(0)
                exit()

    for now in range(idx, N):
        if used[now]:
            continue
        used[now] = True
        dfs(count + 1, now + 1)
        used[now] = False

dfs(0, 0)
print(answer)

조합을 구할 때 순열을 구하는 것과 동일한 시간을 소모시키지 말자.

 

아래는 itertools의 combination함수를 이용하여 구현을 해봤다.

import sys
import itertools

N = int(sys.stdin.readline().rstrip())
power = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
player = [i for i in range(N)]
total_player = set(range(0, N))
answer = 10000
candidate = []

for team in itertools.combinations(player, N//2):
    candidate.append(team)


for idx in range(len(candidate)//2):
    START, LINK = 0, 0

    team = candidate[idx]
    stat_A = 0  # A팀 능력치
    for j in range(N // 2):
        member = team[j]  # 멤버
        for k in team:
            START += power[member][k]  # 멤버와 함께할 경우의 능력치들

    # A를 제외한 나머지 팀
    team = candidate[-idx - 1]
    stat_B = 0
    for j in range(N // 2):
        member = team[j]
        for k in team:
            LINK += power[member][k]

    answer = min(answer, abs(START - LINK))

print(answer)

조합을 미리 구현하는 경우 1번째 후보와 마지막 후보는 A팀과 B팀의 멤버가 교체되는 것이기 때문에 굳이 2번 체크할 필요가 없어 cadidate의 절반까지만 체크하면 된다.

더 적은 시간으 소요되었지만 모듈을 사용할 수 없는 경우도 있으니 두가지 방법을 다 알아놓는 것이 좋을 것 같다.