[백준/20044/파이썬] Project Teams - Greedy

---

소스코드

n = int(input())

student = list(map(int,input().split()))

student.sort()

answer = []

for i in range (2*n):

  answer.append(student[i] + student[2*n-i-1])

print(min(answer))

---

알고리즘

만약 친구들끼리 게임을 하는데 모두 다 다른 능력치를 가지고 2인 팀을 이루어서 게임을 한다면 어떤게 가장 공평한 팀일까?

위와 같은 생각을 모두 어렸을적 한번은 해봤을 것이다.

 

이번 문제가 이런 식으로 진행이 되었다.

 

1번부터 2n번까지의 친구들이 있고 n개의 팀이 나와야 하는데

 

국룰은 1번과 2n번, 2번과 2n -1번, 3번과 2n-2번 ... -> 이렇게 팀이 되는것이다.

 

이 문제도 이렇게 하면 될 것 같아서 풀었는데 이게 웬걸 정답이었다.

 

그렇면 왜 정답일까?

 

정답이 되는 숫자 x1, x2가 있다고 생각을 해보자

 

x1 + x2 < A1 + A2 (A_i는 x1, x2를 제외한 모든 숫자)를 만족하는 애들 중에서 가장 큰 수를 리턴을 해야한다.

 

예를 들어 [1, 5, 7, 8]이 있다

 

나올 수 있는 쌍은 (1, 5), (1, 7), (1, 8), (5, 7), (5, 8), (7, 8)인데 합을 보면 각각 6, 8, 9, 12, 13, 15이다.

최소 - 나머지

6 - 15

8 - 13

9 - 12 인 셈인데

 

>> 우리는 둘 사이가 가장 작은 애를 리턴을 해야한다는 것을 알 수 있다.

 

>> 무슨 소리냐 최소가 가장 크기 위해서는 나머지의 합이 작아져야 한다라는 소리이다. 

 

>> 이해가 안간다면 그렇게 생각을 해보자 전체 합은 일정하기 때문에

ex) 100이라고 치면 최소가 40이 되면 나머지는 60, 49가 되면 51 이런식으로 서로 연관이 되어있기 때문이다.

 

따라서 우리는 전통적으로 팀을 나눴던 방식이 그리디적으로 타당하다고 생각할 수 있다.

 

코드는 다음과 같은 알고리즘을 가지고 있다.

 

1. 입력된 리스트 오름차순 정렬

2. 1번과 마지막 번 숫자를 더해가며 answer 리스트에 저장

3. 그 답 중 최소 값 출력