[알고리즘] 백준 20300번 문제 - 서강근육맨 (그리디)

date

Nov 27, 2023

slug

al-10

author

status

Public

[Silver III] 서강근육맨 - 20300

문제 링크

성능 요약

메모리: 110556 KB, 시간: 124 ms

분류

그리디 알고리즘, 정렬

문제 설명

로니 콜먼 동영상을 보고 보디빌더가 되기로 결심한 향빈이는 PT 상담을 받으러 서강헬스클럽에 갔다. 향빈이가 서강헬스클럽을 선택한 이유는 PT를 받을 때 사용하는 운동기구를 회원이 선택할 수 있다는 점 때문이다. 하지만, 서강헬스클럽은 항상 사람이 많아서 PT를 한 번 받을 때 운동기구를 최대 두 개까지만 선택할 수 있다.

헬스장에 있는 N개의 운동기구를 한 번씩 사용해보고 싶은 향빈이는 PT를 받을 때마다 이전에 사용하지 않았던 운동기구를 선택하기로 계획을 세웠다. 그리고 비용을 절약하기 위해 PT를 받을 때 운동기구를 되도록이면 두 개를 사용하기로 했다. 예를 들어, 헬스장에 총 10개의 운동기구가 있을 경우 PT를 5번 받으면 모든 기구를 다 사용할 수 있다. 9개의 운동기구가 있는 경우에도 PT를 5번 받지만, 마지막 PT를 받을 때는 운동기구를 하나만 사용한다.

하지만 향빈이는 운동기구를 선택하다가 큰 고민에 빠졌다. 왜냐하면 운동기구마다 근손실이 일어나는 정도가 다르기 때문이다. 어떤 운동기구는 자극이 잘 안 와서 근손실이 적게 일어나는데, 어떤 운동기구는 자극이 잘 와서 근손실이 많이 일어난다. 근손실이 죽음보다 무서운 향빈이는 PT를 한 번 받을 때의 근손실 정도가 M을 넘지 않도록 하고 싶다. 이때, M의 최솟값을 구해보자. 참고로, 운동기구를 두 개 사용해서 PT를 받을 때의 근손실 정도는 두 운동기구의 근손실 정도의 합이다.

입력

첫째 줄에 서강헬스클럽에 비치된 운동기구의 개수를 나타내는 정수 N이 주어진다. (1≤N≤10 0001≤N≤10 000)

둘째 줄에는 각 운동기구의 근손실 정도를 나타내는 정수 t1,t2,⋯,tN 가 주어진다. (0≤ti≤10180≤ti≤1018)

출력

M의 최솟값을 출력한다.

예제 입력 1


5
1 2 3 4 5

예제 출력 1

풀이 코드


import sys
input = sys.stdin.readline

n = int(input())
loss = list(map(int, input().split()))
loss.sort()

result = loss[-1]
if n%2 == 1:
    for i in range(n//2):
        tmp = loss[i]+loss[n-i-2]
        if result < tmp:
            result = tmp
elif n%2 == 0:
    for i in range(n//2):
        tmp = loss[i]+loss[n-i-1]
        if result < tmp:
            result = tmp
            
print(result)

설명

⭐ 핵심

짝수인 경우와 홀수인 경우를 나눠서 생각하기

n이 홀수라면 운동기구를 하루만 사용하는 날 근손실이 최대로 일어나는 기구를 사용해야 한다.

이 문제는 짝수인 경우와 홀수인 경우를 나눠서 생각한다.

운동기구가 홀수인 경우에는 2개씩 사용하다 보면 하나는 남게 되기 때문이다.(ex) 운동기구가 9개인 경우에는 2개씩 사용하면 pt 5번 할때 [2,2,2,2,1]개씩 사용할 수 있음. 운동기구가 10개면 2개씩 사용하면 pt 5번 할 때 모두 2번씩 가능함.)

그리고 하나의 운동기구를 하는 날의 그 운동기구가 가장 근손실 정도가 큰 운동기구일 때 근손실 정도를 줄일 수 있다.

리스트를 오름차순으로 정렬한 후에 가장 마지막 원소(가장 큰 값)를 result에 저장한다.

그리고 남은 리스트에서 가장 작은 값과 가장 큰 값끼리 더한다.

그때마다 result값과 더한 값을 비교해주어 더한 값이 더 크다면 result 값을 변경하도록 한다.