boj 20300 :

문제 주소: https://www.acmicpc.net/problem/20300

난이도: silver 3

1.문제설명

• 헬스장에 운동기구 N개가 있다.
• 하루에 2개씩 묶어서하려고한다, 홀수개면 나머지 한개는 그것만 한다.
• 이때 운동기구마다 근손실이 나는 정도가 있다.
• 하루에 근손실의 정도가 M이 넘지 않도록 하려고 한다.
• 이때 M의 최소값은?

2.문제해결 아이디어.

• M을 최소값이라고 해서 조금 헷깔리는데
• 사실 어떻게보면 sup(supremum : Least upper bound)를 구하는게 아닐까?
• 근손실의 정도로 정렬한다음에
• 근손실이 가장 많이나는 운동 + 적게나는 운동을 조합하면된다.

3.문제접근법

• 기구가 짝수개, 홀수개일때를 나눠야한다
• 짝수개라면 정렬한다음
  • (0번째 N번째), (1번째 N-1번째) .... 이렇게 묶어서 이들중 가장 큰 값이 정답이다.
• 홀수개라면 정렬한다음 마지막원소는 빼고
  • (0번째 N-1번째), (1번째, N-2번째)... 이렇게 묶어서 이들중 최대값과 마지막원소를 비교해서 더 큰 값이 정답.

4.특별히 참고할 사항

• 그리디 문제는 많은 사고를 요하지 않는것같다.
• 욕심쟁이는 단순하다...
• 평소 사는것처럼... 단순하게..!!!

5.코드구현

N = int(input())
ans = 0
workout = list(map(int, input().split()))
workout.sort()

if N%2 == 0:
    mid = N//2
    for i in range(0, mid):
        _temp = workout[i] + workout[N-1-i]
        ans = max(ans,_temp)
else:
    mid = (N-1)//2
    for i in range(0, mid):
        _temp = workout[i] + workout[N - 2 - i]
        ans = max(ans, _temp)
        ans = max(ans, workout[-1])

print(ans)