[BOJ] 서강근육맨

서강근육맨

문제

서강헬스클럽은 항상 사람이 많아서 PT를 한 번 받을 때 운동기구를 최대 두 개까지만 선택할 수 있다.
헬스장에 있는 NN개의 운동기구를 한 번씩 사용해보고 싶은 향빈이는 PT를 받을 때마다 이전에 사용하지 않았던 운동기구를 선택하기로 계획을 세웠다. 그리고 비용을 절약하기 위해 PT를 받을 때 운동기구를 되도록이면 두 개를 사용하기로 했다. 예를 들어, 헬스장에 총 110개의 운동기구가 있을 경우 PT를 55번 받으면 모든 기구를 다 사용할 수 있다. 99개의 운동기구가 있는 경우에도 PT를 55번 받지만, 마지막 PT를 받을 때는 운동기구를 하나만 사용한다.
또한 근손실이 죽음보다 무서운 향빈이는 PT를 한 번 받을 때의 근손실 정도가 MM을 넘지 않도록 하고 싶다. 이때, MM의 최솟값을 구해보자. 참고로, 운동기구를 두 개 사용해서 PT를 받을 때의 근손실 정도는 두 운동기구의 근손실 정도의 합이다.

 

 

해결방법

1. 탐욕 알고리즘 (Greedy)
2. 오름차순으로 정렬한다.
3. 운동기구의 수가 홀수일때는 가장 큰 값 제외하고, 반복문을 통해 가장 큰 값과 가장 작은 값의 합을 리스트에 넣어준다.
4. 운동기구의 수가 짝수일때는 제외하는 값 없이 바로 반복문을 통해 가장 큰 값과 가장 작은 값의 합을 리스트에 넣어준다.

 

소스코드

N = int(input())
health = list(map(int, input().split()))
health.sort()
tmp = []

if (N % 2 == 1):
    tmp.append(max(health))
    health.remove(max(health))
    for i in range(N-1):
        tmp.append(health[i] + health[N-i-2])

if (N % 2 == 0):
    for i in range(N):
        tmp.append(health[i] + health[N-i-1])

print(max(tmp))