백준 20044 Project Teams Python: 팀 최솟값을 최대화하는 정렬

백준 20044의 목표는 팀 능력치 합의 최댓값을 최소화하는 것이 아니다. 2N명을 두 명씩 묶어 N개 팀을 만들고, 그중 가장 낮은 팀 합 S_m을 최대화하는 문제다. 오름차순 정렬 뒤 가장 작은 값과 가장 큰 값을 차례로 짝지어 각 합의 최솟값을 출력하면 된다.

오름차순: 1 5 7 8
팀 구성: (1, 8), (5, 7)
팀 합:   9, 12
최솟값:  9

코드가 계산하는 목적함수

각 팀 G_i의 능력치 합을 w(G_i)라고 하면 문제는 다음 값을 최대화하라고 한다.

S_m = min(w(G_1), w(G_2), ..., w(G_N))

즉, 가장 약한 팀의 합을 가능한 한 크게 만드는 max-min 문제다. 한 팀만 매우 강하게 만드는 것보다 바닥값을 끌어올리는 공정한 pairing이 목적이다.

왜 가장 작은 값과 가장 큰 값을 묶을까

정렬한 능력치를 a_0 < a_1 < ... < a_(2N-1)이라 하자. 가장 작은 a_0은 누군가와 반드시 한 팀이 된다. 이 팀의 합을 가장 크게 만들 수 있는 partner는 가장 큰 a_(2N-1)이다.

이 설명만으로 greedy proof가 끝나는 것은 아니다. 어떤 최적 pairing에서 a_0가 a_j와, 가장 큰 값 a_(2N-1)이 a_k와 짝이라고 하자. 두 팀을 다음처럼 바꾼다.

기존: (a_0, a_j), (a_k, a_(2N-1))
교환: (a_0, a_(2N-1)), (a_j, a_k)

기존 두 팀 합이 어떤 기준 X 이상이었다면 교환한 두 팀도 X 이상이다.

• a_0 + a_(2N-1) ≥ a_0 + a_j ≥ X
• a_j + a_k ≥ a_0 + a_j ≥ X because a_k ≥ a_0

따라서 최적해를 해치지 않고 양 끝을 한 팀으로 고정할 수 있다. 남은 값에서도 같은 교환을 반복하면 (a_0,a_(2N-1)), (a_1,a_(2N-2)) 형태의 pairing에 최적해가 존재한다.

Python 풀이

n = int(input())
abilities = list(map(int, input().split()))
abilities.sort()

answer = min(
    abilities[i] + abilities[2 * n - 1 - i]
    for i in range(n)
)

print(answer)

원래 코드의 min 갱신 방향은 맞았다. 잘못된 것은 코드가 아니라 ‘팀 합의 최댓값을 최소화한다’는 문제 설명이었다. 이 code는 양 끝으로 구성한 N개 팀 합 중 최솟값을 계산한다.

경계와 복잡도

문제 조건은 1 ≤ N ≤ 5,000, 각 능력치는 1 이상 100,000 이하이고 모두 다르다.

• N=1: 두 사람의 합을 그대로 출력한다.
• 가능한 팀 합의 상한은 200,000이다.
• 정렬: O(N log N) — 원소 수가 2N이어도 big-O는 같다.
• pairing 확인: O(N)
• 입력 list 저장: O(N). Python sort는 구현상 임시 memory를 추가로 사용할 수 있다.

greedy 결과는 N=1..4의 서로 다른 작은 능력치 random input 2,000개에서 모든 perfect matching을 열거한 결과와 비교해 같음을 확인했다. 이 검증은 proof를 대신하지 않지만 index와 최솟값 갱신 실수를 찾는 데 도움이 된다.

정렬 뒤 선택량과 고정된 벌점을 분리하는 또 다른 문제는 백준 20186 수 고르기에서 이어서 볼 수 있다.

참고 자료

• 백준 20044 Project Teams