[백준/파이썬]20300 서강근육맨

문제

https://www.acmicpc.net/problem/20300

20300번: 서강근육맨

 

PT 한 번에 두 가지 운동 기구를 사용할 수 있고, 각 운동 기구의 근손실 값이 주어진다.

 

이때, 모든 PT를 받았을 경우(모든 운동 기구를 사용했을 경우) 근손실을 최소로 하는 값을 출력하는 문제다.

 

 

 

처음 문제를 보고 이분 탐색 문젠가 싶었다가 유혹을 참지 못하고 알고리즘 분류를 봤다.

 

분류를 보니 그리디 문제였고 이를 보자마자 생각한 방법은 정렬된 각 운동기구의 근손실 배열을 앞, 뒤에서부터 중앙으로 인덱스를 옮기면서 더한 값 중 최대가 되는 값이 모든 운동기구를 사용했을 때의 최소 근손실 값이겠거니 했다.

 

예제 입력 1을 예시로

5

1 2 3 4 5

라는 입력값이 들어올 때는 N(5)이 홀수다. 

sum = arr[i] + arr[n-i-2]

에서 sum이 최대가 되는 값이 답이다.

 

N이 짝수인 경우에는

6

1 2 3 4 5 6

sum = arr[i] + [n-i-1]

에서 sum이 최대가 되는 값이 답이다.

 

 

근데 이 문제의 테스트 케이스가 많이 약한 것 같다.

 

1

1

의 입력의 경우 2가 출력되는 코드도 정답 처리된다.

 

또한 

5

0 0 0 0 5

의 경우 정답이 5가 되어야 하지만 0 이 출력되는 코드도 정답처리된다.

 

그게 내 코드다.. 나중에 재채점 되면 고쳐야겠다.

정답??

n = int(input())

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

a = 1 if n % 2 == 0 else 2
for i in range(n//2+1) :
    
    sum_ = arr[i] + arr[n-i-a]

    if ans < sum_ :
        ans = sum_

print(ans)