그리디(유형정리) - 백준 20300

20300번: 서강근육맨 (acmicpc.net)

20300번: 서강근육맨

 

문제

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

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

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

입력

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

둘째 줄에는 각 운동기구의 근손실 정도를 나타내는 정수 �1,�2,⋯,��$t_1, t_2, \cdots, t_N$가 주어진다. (0≤��≤1018$0 \leq t_i \leq 10^{18}$)

출력

 �$M$의 최솟값을 출력한다.

예제 입력 1 복사

5
1 2 3 4 5

예제 출력 1 복사

5

 

문제를 보면 이게 왜 그리디 알고리즘인지 대번에 파악이 가능하다. 어떻게든 최소의 근손실을 만들겠다는 의미이다.

 

처음에 문제를 보고 분명 머릿속으로는 알겠는데 어떻게 1과 4를 더하게 만들 수 있는지 생각이 들지 않았다.

자세히 보다보니 홀, 짝으로 나누면 간단한 부분이었다.

 

※ 알고리즘

1. N을 입력받고, 근손실 정도를 list로 입력받는다.

2. 근손실 list를 오름차순으로 정렬해주고, 하나만 남을 때를 대비해서 result 변수에 최댓값을 넣어준다.

3. 홀수 일 때, for문으로 temp 변수에 원하는 값을 더하고, temp보다 result가 작다면 result변수를 temp 변수로 갱신한다. 짝수에서도 정확히 같은 과정을 반복한다.

 

temp 변수를 만들 때, 홀수일 때와 짝수일 때를 잘 구분하여 최댓값의 인덱스를 더해주어야 한다.

 

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

result = loss[-1]
if N % 2 == 1:
    for i in range(N//2):
        temp = loss[i] + loss[N-i-2]   # i=0, 5-0-2 = 3 -> index 3 : 4
        if result < temp:
            result = temp

else:
    for i in range(N//2):
        temp = loss[i] + loss[N-i-1]
        if result < temp:
            result = temp

print(result)

 

이렇게 해결 가능!!!