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

문제 링크

14889번: 스타트와 링크

 

접근 방법

• N명의 사람을 두 팀으로 나누어 두 팀 간 능력치 차이의 최솟값을 구하는 문제
• N은 최대 20명 → 완전탐색(Brute Force)이 가능
• N명 중 N/2명을 선택 → 조합 문제

이번 풀이에서는 백트래킹을 이용해 조합을 구성한다.

 

핵심 로직

1️⃣ 백트래킹으로 N명 중 N/2명 선택
2️⃣ 선택된 팀과 나머지 팀으로 구분
3️⃣ 두 팀의 능력치 계산 후 최소 차이 갱신
4️⃣ 차이가 0이면 즉시 종료

 

코드

import sys

input = sys.stdin.readline

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

visited = [False] * N
min_diff = float('inf')

def backtrack(depth, idx):
    global min_diff

    # 팀 구성 완료 (N/2명)
    if depth == N // 2:
        start_team = []
        link_team = []

        for i in range(N):
            if visited[i]:
                start_team.append(i)
            else:
                link_team.append(i)

        start_sum = 0
        link_sum = 0

        # 팀 능력치 계산
        for i in range(N // 2):
            for j in range(N // 2):
                if i != j:
                    start_sum += S[start_team[i]][start_team[j]]
                    link_sum += S[link_team[i]][link_team[j]]

        diff = abs(start_sum - link_sum)
        min_diff = min(min_diff, diff)

        if min_diff == 0:
            print(0)
            sys.exit(0)

        return

    # 백트래킹으로 조합 구성
    for i in range(idx, N):
        if not visited[i]:
            visited[i] = True
            backtrack(depth + 1, i + 1)
            visited[i] = False

# 시작
backtrack(0, 0)
print(min_diff)

 

 

핵심 정리 (디테일하게)

• 조합 구성 (백트래킹)
  • visited[] 배열 사용 (선택 여부 표시)
  • index 기준으로 재귀 호출 → 중복 없이 조합 구성
• 팀 능력치 계산
  • start_team, link_team 으로 나누어
  • 두 팀 간 모든 (i, j) 쌍 능력치 합산
• 최솟값 갱신
  • min_diff 값 계속 업데이트
  • 차이가 0이면 최적해 → 즉시 종료
• 시간 복잡도
  • C(N, N/2) 수준 → 충분히 가능 (N ≤ 20)

 

간단한 회고

• 백트래킹을 익히기 좋은 문제였다
• 조합을 직접 백트래킹으로 구현하면 combinations 같은 라이브러리 없이도 풀 수 있는 실력이 된다
• visited 배열과 index를 이용한 조합 설계는 다른 문제 (부분집합, 순열, 조합) 에서도 자주 쓰이는 기법