백준 20044번: Project Teams 문제 풀이

1. 문제 개요

백준 20044번, Project Teams 문제는 주어진 개발자들의 능력치를 이용해 팀을 구성하고, 각 팀의 능력치 합 중 최댓값을 최소화하는 것이 목표입니다. 이를 효율적으로 해결하기 위해 정렬과 양 끝의 포인터를 활용하는 접근법에 대해 알아보겠습니다.

---

2. 접근 방법

문제를 효율적으로 해결하기 위해 다음과 같은 로직을 설계했습니다.

1. 정렬하기
   능력치 리스트를 오름차순으로 정렬하여, 가장 작은 값과 큰 값을 쌍으로 묶으면 팀 능력치의 최대값을 최소화할 수 있습니다.
2. 양끝 더해서 최솟값 계산
   각 팀의 능력치를 구하기 위해 정렬된 리스트의 양 끝 값을 더합니다.
3. 최솟값 비교 반복
   가능한 모든 팀 조합의 능력치 중 최대값의 최솟값을 구합니다. 이를 위해 NN번 반복하며 최솟값을 업데이트합니다.

---

3. 구현 코드

다음은 Python으로 작성한 코드입니다.

# 입력 받기
N = int(input())  # 팀의 수
num_list = list(map(int, input().split()))  # 개발자의 능력치 리스트

# 능력치 리스트 정렬
num_list.sort()

# 최솟값 초기화
answer = float('inf')  # 매우 큰 값으로 초기화

# 팀 능력치 계산
for i in range(N):
    # 양 끝 값을 더한 결과 중 최솟값 갱신
    answer = min(num_list[i] + num_list[2 * N - 1 - i], answer)

# 결과 출력
print(answer)

---

4. 주요 개념

(1) 정렬을 활용한 팀 구성
정렬을 통해 가장 작은 값과 가장 큰 값을 묶는 것이 최적의 팀 구성 방법입니다. 예를 들어, 능력치가 [1, 2, 3, 4]라면, 쌍을 (1+4), (2+3)으로 묶는 것이 최적입니다.

(2) 포인터 활용
양 끝 값의 합을 계산하기 위해 하나는 리스트의 맨 앞(i), 다른 하나는 맨 뒤(2*N - 1 - i)에서 시작하여 점진적으로 좁히는 방식입니다.

---

5. 장단점

장점

• 시간복잡도 O(Nlog⁡N)O(N \log N)로 효율적입니다. 정렬 후 NN번 반복하기 때문입니다.
• 간단한 구현으로 최적해를 도출할 수 있습니다.

단점

• 입력이 매우 클 경우, 정렬 과정에서 시간 소모가 발생할 수 있습니다.

---

6. 적용 예시

입력 예시

2
1 2 3 4

실행 과정

1. 입력 리스트를 정렬: [1, 2, 3, 4]
2. 양 끝 값 계산:
   • 첫 번째 쌍: 1+4=5
   • 두 번째 쌍: 2+3=5
3. 최댓값 중 최솟값: 5

출력 결과

5

---

7. 결론

이 문제는 정렬과 최댓값 최소화 전략을 학습하기에 적합한 예제입니다. 간단한 접근법으로도 효율적으로 해결 가능하며, 실전 코딩 테스트에서 자주 나오는 유형입니다.

 

백준, 20044, Project Teams, Python, 알고리즘, 정렬, 문제풀이, 파이썬