[백준 20300번] 서강근육맨 (Python)

> 파이썬, 그리디 알고리즘, 정렬

 

 

 

 

📖 문제 : 서강근육맨 (Python)

 

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

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

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

 

 

 

입력

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

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

 

 

출력

 M의 최솟값을 출력한다.

 

 

 

예제 입력 1 

5
1 2 3 4 5

 

예제 출력 1 

5

PT 첫째 날에 1과 4를 선택하고, 둘째 날에 2와 3을 선택하고, 마지막 날에 5를 선택하면 M은 5가 되며, 이때가 M이 최소일 때이다.

 

 

 

 

 

내 코드

if __name__ == "__main__":

    N = int(input())
    protein = list(map(int, input().split()))

    protein.sort()
    temp = []

    if len(protein) % 2 == 0:
        for i in range(len(protein) // 2):
            temp.append(protein[i] + protein[N - 1 - i])

        print(max(temp))
    else:
        for i in range(len(protein) // 2):
            temp.append(protein[i] + protein[N - 2 - i])

        temp.append(protein[-1])
        print(max(temp))

 

 

 

Point ! ⭐️ 

• 무조건 하루에 2개씩 운동기구를 선택하여, 모든 운동기구를 사용했을 때의 매일매일 얻는 근손실의 합이 최소가 되어야하므로,
  
  

5
1 6 3 4 9

운동기구의 수가 짝수인지 홀수인지에 따라 경우를 나눌 수 있는데

위의 예제를 보면, 운동기구의 수가 홀수 개이다.
운동기구의 근손실 값들을 오름차순으로 정렬하여, 근손실의 합들이 최소가 되게 하기 위해서는

1, 6, 3, 4, 9 -> (오름차순 정렬) -> 1, 3, 4, 6, 9

(1, 6) (3, 4) (9) 이런식으로

가장 끝값을 하나 남겨두고 2개씩 짝지은 후 그 중에서 최댓값을 찾는 것이 근손실의 합의 최솟값을 구할 수 있다.

왜냐하면, 만약 (1, 9) 을 묶게 되면 가장 큰 값에 또 다른 값을 더하게 되므로 근손실의 합이 더 커질 수 있다는 것이다.

 

운동기구가 짝수 개일 때에는 각 끝값 두개씩 운동기구를 사용하여 그 중에서 최댓값을 구하면 된다.
1, 2, 3, 4, 5, 6 이라고 하면,
(1, 6), (2, 5), (3, 4) 이 값들 중 최댓값 7이 근손실의 합의 최솟값이된다.
왜냐하면, 가장 큰 값을 가장 작은 값과 묶어줘야 가장 그래도 그나마 최솟값으로 만들 수 있기 때문이다.

 

 

 

 

 

 

백준

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

20300번: 서강근육맨