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

이번 글에서는 백준 14889번 문제 “스타트와 링크”를 함께 해결해 보겠습니다. 이 문제는 N명의 사람들이 두 팀으로 나누어질 때, 두 팀의 능력치 차이를 최소화하는 문제입니다.

 

1. 문제 설명

1) 문제 개요

• N명의 사람들이 두 팀으로 나뉘어 게임을 합니다.

• 각 사람마다 다른 사람과 팀을 이루었을 때의 능력치가 주어집니다.

• 두 팀의 능력치 차이를 최소화하는 것이 목표입니다.

 

2) 입력

• 첫 번째 줄에 사람의 수 N이 주어집니다. (4 ≤ N ≤ 20, N은 짝수)

• 두 번째 줄부터 N개의 줄에 걸쳐 각 사람의 능력치가 주어집니다.

 

3) 출력

• 두 팀의 능력치 차이의 최솟값을 출력합니다.

 

2. 접근법

1) 입력받기

• sys.stdin.readline을 사용하여 입력 속도를 높입니다.

• 첫 번째 줄에서 사람의 수 N을 입력받습니다.

• 다음 N개의 줄에서 능력치 배열을 입력받습니다.

 

2) 그래프 구성

• 2차원 리스트를 사용하여 각 사람 간의 능력치를 저장합니다.

 

3) 재귀 및 백트래킹을 이용한 팀 나누기

• 재귀 함수와 백트래킹을 사용하여 모든 가능한 팀 조합을 탐색합니다.

• 두 팀의 능력치 차이를 계산하여 최소값을 갱신합니다.

 

3. 정답 코드

import sys
input = sys.stdin.readline

# N: 총 인원 수
N = int(input())

# 능력치 배열 초기화
arr = []
for _ in range(N):
    arr.append(list(map(int, input().split())))

# 최소 차이를 저장하기 위한 변수, 초기값을 매우 큰 값으로 설정
ans = sys.maxsize

# 팀을 나누는 재귀 함수
def rec(n, teamA, teamB):
    global ans
    
    # 모든 인원을 다 배정했을 때
    if n == N:
        # 팀A와 팀B의 인원 수가 같을 경우에만 계산
        if len(teamA) == len(teamB):
            asum = bsum = 0
            
            # 각 팀의 능력치를 계산
            for i in range(N // 2):
                for j in range(N // 2):
                    asum += arr[teamA[i]][teamA[j]]
                    bsum += arr[teamB[i]][teamB[j]]
            
            # 능력치 차이의 최소값 갱신
            ans = min(ans, abs(asum - bsum))
        return

    # 현재 인원을 팀A에 추가하고 다음 인원을 처리
    rec(n + 1, teamA + [n], teamB)
    
    # 현재 인원을 팀B에 추가하고 다음 인원을 처리
    rec(n + 1, teamA, teamB + [n])

# 초기 호출: 인원 n=0에서 시작, 팀A와 팀B는 빈 리스트로 시작
rec(0, [], [])

# 최소 능력치 차이 출력
print(ans)

 

4. 코드 설명

 

1) 입력 받기

• N과 능력치 배열을 입력받고, arr에 저장합니다.

 

2) 그래프 구성

• arr은 N x N 크기의 2차원 리스트로, 각 사람 간의 능력치를 저장합니다.

 

3) 재귀 및 백트래킹을 이용한 팀 나누기

• rec 함수는 현재 인원 n과 현재까지 배정된 팀 teamA, teamB를 인수로 받습니다.

• 모든 인원을 다 배정했을 때(n == N), 두 팀의 인원이 같으면 능력치 차이를 계산합니다.

• 각 팀의 능력치 합을 계산하고, 그 차이가 최소가 되도록 ans를 갱신합니다.

• 현재 인원을 teamA에 추가하거나, teamB에 추가하여 다음 인원을 처리하도록 재귀 호출합니다.

 

4) 결과 출력

• 계산된 최소 능력치 차이를 출력합니다.

 

예시를 통한 설명

예를 들어, N = 4이고, 능력치 배열이 다음과 같이 주어졌다고 가정합니다.

arr = [

    [0, 1, 2, 3],

    [1, 0, 4, 5],

    [2, 4, 0, 6],

    [3, 5, 6, 0]

]

 

단계 1: 초기 상태

n = 0

teamA = []

teamB = []

 

단계 2: 재귀 호출을 통해 팀 나누기

1. n = 0인 사람을 teamA에 추가

n = 1

teamA = [0]

teamB = []

 

2. n = 1인 사람을 teamA에 추가

n = 2

teamA = [0, 1]

teamB = []

 

3. n = 2인 사람을 teamA에 추가 (이 경우는 배제됨, 팀 인원수 불균형)

4. n = 2인 사람을 teamB에 추가

n = 3

teamA = [0, 1]

teamB = [2]

 

5. n = 3인 사람을 teamA에 추가 (이 경우는 배제됨, 팀 인원수 불균형)

6. n = 3인 사람을 teamB에 추가

n = 4

teamA = [0, 1]

teamB = [2, 3]

 

단계 3: 능력치 계산

• teamA = [0, 1]의 능력치 합 (asum)

asum = arr[0][0] + arr[0][1] + arr[1][0] + arr[1][1]

     = 0 + 1 + 1 + 0

     = 2

 

• teamB = [2, 3]의 능력치 합 (bsum)

bsum = arr[2][2] + arr[2][3] + arr[3][2] + arr[3][3]

     = 0 + 6 + 6 + 0

     = 12

 

• 능력치 차이

abs(asum - bsum) = abs(2 - 12) = 10

 

******

Initial state:

  teamA: []

  teamB: []

 

1. Add person 0 to teamA:

  teamA: [0]

  teamB: []

 

2. Add person 1 to teamA:

  teamA: [0, 1]

  teamB: []

 

3. Add person 2 to teamB:

  teamA: [0, 1]

  teamB: [2]

 

4. Add person 3 to teamB:

  teamA: [0, 1]

  teamB: [2, 3]

 

Calculate abilities:

  teamA: 2

  teamB: 12

 

Difference:

  abs(2 - 12) = 10

******

 

5. Github으로 확인

coTest/BOJ/BOJ01_07_02_14889.py at main · pcy4196/coTest