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

문제

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

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

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

입력

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

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

출력

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

예제 입력 1 복사

5
1 2 3 4 5

예제 출력 1 복사

5

 

 

 

[소스 코드]

 

운동기구 개수가 홀수일 때와 짝수일 때를 나눠야 함도 알았고,

최솟값을 구하기 위해서는 가장 작은 수와 가장 큰 수를 더해야 함도 알았지만

이걸 너무 그대로 코드에 적용시켜서 처음 풀었을 때는 틀렸다.

2개의 값을 더한 것들 중에 최댓값을 구하는 과정 없이 결론을 내서 틀렸었다.

 

홀수인 경우에는 2개씩 사용하다 보면 하나는 남게 된다. 그 운동기구가 가장 근손실 정도가 큰 운동기구일 때 

근손실 정도를 줄일 수 있으므로 리스트를 오름차순으로 정렬한 후에 가장 마지막에 원소를 result에 저장한 후에

나머지 원소들을 2개씩 더한 값과 비교해준다.

2개씩 더할 때는 가장 작은 값과 가장 큰 값을 더해주어 합의 최솟값을 구하도록 한다.

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

 

운동기구 개수가 홀수이고 짝수일 때의 차이는 운동기구가 하나 남느냐 안 남느냐의 차이이므로

하나의 운동기구를 사용하는 날은 가장 근손실 값이 큰 운동기구를 사용해야 한다는 것과

인덱스 값만 잘 고려해주면 어렵지 않다.

 

import sys 

input = sys.stdin.readline

n = int(input()) #운동기구 개수
lose = list(map(int, input().split()))
lose.sort() #오름차순으로 정렬

result = lose[-1] #가장 큰 근손실 정도
if n%2==1: #홀수일 경우 하나만 사용하는 기구는 근손실이 가장 큰 기구여야 함
    for i in range(n//2): #2개씩 더할 예정이므로 절반만
        tmp = lose[i]+lose[n-i-2] #리스트에서 제일 작은 값과 제일 큰 값을 더함
        if result < tmp: #result는 현재 가장 큰 값, tmp값이 더 크다면 바꿔줌
            result = tmp
elif n%2==0: #짝수일 경우에도 같은 방법으로 해준다
    for i in range(n//2):
        tmp = lose[i]+lose[n-i-1]
        if result < tmp:
            result = tmp
    
    
print(result)