[백준/그리디] 20300번 : 서강근육맨

- 문제 : https://www.acmicpc.net/problem/20300

 

 

정답 풀이

이 문제는 다음과 같은 과정으로 진행된다.

 

• 주어진 배열의 원소들 중 한 번에 2개의 원소씩 짝지어 값을 더한다. 이때 각 값의 합이 최소가 되도록 해야한다 -> (그리디)
• 두 숫자의 합이 최소가 되기 위해서는, 원소를 오름차순 정렬한 후 양쪽에 있는 값을 더하면 된다. [i번째] 원소 +  [n - 1 -i ]번째 원소
• 이 때 반복문 범위는 인덱스 0부터 절반까지 진행한다. 절반에서 원소가 정해지면 반대편은 자동으로 정해지기 때문이다. 값 중복하지 않기 위함도 있다. 
• 배열 원소 개수가 홀수인 경우에는 두 개씩 묶고 하나의 원소가 남기 때문에 아래와 같이 추가 연산이 필요하다.
  • 모든 원소가 짝지어지고 하나의 원소가 남는데, 그 원소가 가장 큰 숫자이면 된다. 배열을 오름차순 정렬했으므로 가장 오른쪽 값만   result에 넣는다.

 

n = int(input())
arr = sorted(list(map(int, input().split())))

result = []
if n % 2 == 1:
    result.append(arr.pop())

m = len(arr)
for i in range(m // 2):
    result.append(arr[i] + arr[m - 1 - i])
    
    
print(max(result))