[python] 백준 20044번 Project Teams

문제 풀이

첫째 줄에 팀 수(한 팀당 학생 2명)

둘째 줄에 학생들의 코딩 역량 (한 팀당 학생 2명이기에 팀 수 X2 만큼의 역량 개수가 주어진다.)

 

예제 1에서 1 7 5 8 이 입력으로 들어왔을 때

팀 당 역량이 최대화되기 위해서는 (1, 8), (7,5)로 묶일 수 있다.

그리고 역량의 합이 최소가 되도록 하면 된다.

 

내가 생각한 방법은

해당 역량을 순서 없이 받아왔다고 가정하면 sorted()로 오름차순 정렬을 시켜준 후

투 포인터를 이용하여 범위를 좁혀 가며 구하는 방식이다.

ex) 역량으로 1 7 3 5 9 2가 들어오면 오름차순 정렬 후 1 2 3 5 7 9 가 된다.

     투 포인터를 이용하면 (1, 9), (2, 7), (3, 5) 이렇게 3팀으로 묶이게 된다.

     팀들의 역량의 합을 구하면 10, 9, 8 이렇게 3팀의 역량의 합이 나온다.

     그 중 최솟값을 출력해주면 된다.

투 포인터를 이용하여 구한 결과값

완성된 코드!!👍😊

import sys

teams = int(input())
ability = sorted(map(int, sys.stdin.readline().split()))
# left는 ablility의 첫번째 원소부터 ->
# right는 ability의 마지막 원소부터 <-
left, right = 0, teams*2 - 1
# 합이 최대일 경우가 199999이다.
# (1 ≤ w(si) ≤ 100,000) 조건을 보면 
# 99,999과 100,000이 들어왔을 때의 최대합이 199999이기 때문이다.
rs = 199999
# 범위를 좁혀 나가기 때문에 left값이 right값보다 작을때만 돌아가도록 해야한다.
while left < right:
    if ability[left] + ability[right] < rs:
        rs = ability[left] + ability[right]
    left += 1
    right -= 1
print(rs)