[백준 14889] 스타트와 링크(python)

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

14889번: 스타트와 링크

스타트와 링크 문제

짝수인 N명의 사람을 2개의 팀으로 나누어 각각의 팀의 능력치의 차이를 최소로 만드는 문제

백트래킹을 활용하거나 조합을 활용해서 풀 수 있다.

⚙️내가 푼 정답코드(백트래킹 활용)

def team(a,n):
    global result
    if a == N//2: # 유망하다면
        start, link = 0, 0 # start 팀, link팀
        for i in range(N):
            for j in range(N):
                if visited[i] and visited[j]: # 만약 i, j 둘다 방문한거라면
                    start += S[i][j] # 스타트팀에 배정
                elif not visited[i] and not visited[j]: # i,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 # 되돌아가
import sys
N = int(sys.stdin.readline())
S = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
visited = [0]*N
result = float('inf')
team(0,0)
print(result)

반응형

⚙️정답코드(조합 활용)

import sys
from itertools import combinations
N = int(sys.stdin.readline())
stat = [list(map(int, sys.stdin.readline().split())) for _ in range(N)]
sum_stat = [sum(i) + sum(j) for i, j in zip(stat, zip(*stat))] # 대각선끼리 합
allstat = sum(sum_stat) // 2 # 모든 값 합의 절반
result = float('inf')
for l in combinations(sum_stat, N//2): # 대각선 합에서 뽑은 2개 중에서
    result = min(result, abs(allstat - sum(l))) # 모든 값의 절반 - 그 뽑은 2개 합의 차 = start팀 - link팀
print(result)

위 두 가지 방식 특성상 처리시간은 백트레킹이 조합 활용보다 백준에 제출해본 기준 60배정도 차이났다.

📌 문제 접근 포인트

# 백트래킹 사용시
1. 백트래킹을 활용해서 만들 수 있는 조합의 경우의 수를 만들어주자. N자리의 모든 갯수를 탐색할 필요 없이 필요한 부분(절반)만 탐색해도 된다.
2. 백트래킹으로 풀이시, 방문여부를 체크할 수 있게 만들어주고, 절반까지만 방문하므로 방문하지 않은 절반은 자연스레 다른 팀으로 나눠주면 된다.
3. 나눠준 팀을 기준으로 팀의 능력치를 각각 배분해서 차이를 구한 후 최소값을 구해보자.

# 조합 사용시
1. 능력치를 보면 행렬 전체의 합이 결국 팀이 가질 수 있는 모든 능력치임을 알 수 있다.
2. 각각의 행과 열의 합을 구해주기 위해서 zip함수를 이용하여 구한 리스트를 만들어주자. 이 합은 n번과 m번이 팀일 때 생기는 모든 능력치의 합이다. 
1행 + 1열 → 1번이 본인과 다른 사람들과 팀을 했을 때 능력치의 합
2행 + 2열 → 2번이 본인과 다른 사람들과 팀을 했을 때 능력치의 합
.....
3. 2번리스트의 합 절반이 1번에서 말한 모든 능력치 임을 알 수 있다.
4. 이제 2번 리스트에서 인원수/2 만큼 뽑는 경우의 수를 구하면 각각의 번호가 팀일 때의 능력치의 합임을 알 수 있다.
5. 전체 모든 능력치와 차이를 구해서 가장 작은 값을 구하면 된다.