그리디 문제입니다.
각 날짜 별 일어나는 근손실을 계산 후, 가장 큰 근손실의 값이 최소가 되게 하는 문제입니다.
문제 자체가 설명하기 조금 헷갈리네요.
실버 3
시간 제한 | 메모리 제한 |
---|---|
1 초 (추가 시간 없음) | 1024 MB |
로니 콜먼 동영상을 보고 보디빌더가 되기로 결심한 향빈이는 PT 상담을 받으러 서강헬스클럽에 갔다. 향빈이가 서강헬스클럽을 선택한 이유는 PT를 받을 때 사용하는 운동기구를 회원이 선택할 수 있다는 점 때문이다. 하지만, 서강헬스클럽은 항상 사람이 많아서 PT를 한 번 받을 때 운동기구를 최대 두 개까지만 선택할 수 있다.
헬스장에 있는
개의 운동기구를 한 번씩 사용해보고 싶은 향빈이는 PT를 받을 때마다 이전에 사용하지 않았던 운동기구를 선택하기로 계획을 세웠다. 그리고 비용을 절약하기 위해 PT를 받을 때 운동기구를 되도록이면 두 개를 사용하기로 했다. 예를 들어, 헬스장에 총 개의 운동기구가 있을 경우 PT를 번 받으면 모든 기구를 다 사용할 수 있다.
개의 운동기구가 있는 경우에도 PT를 번 받지만, 마지막 PT를 받을 때는 운동기구를 하나만 사용한다.
하지만 향빈이는 운동기구를 선택하다가 큰 고민에 빠졌다. 왜냐하면 운동기구마다 근손실이 일어나는 정도가 다르기 때문이다. 어떤 운동기구는 자극이 잘 안 와서 근손실이 적게 일어나는데, 어떤 운동기구는 자극이 잘 와서 근손실이 많이 일어난다. 근손실이 죽음보다 무서운 향빈이는 PT를 한 번 받을 때의 근손실 정도가
을 넘지 않도록 하고 싶다. 이때, 의 최솟값을 구해보자. 참고로, 운동기구를 두 개 사용해서 PT를 받을 때의 근손실 정도는 두 운동기구의 근손실 정도의 합이다.
둘째 줄에는 각 운동기구의 근손실 정도를 나타내는 정수
가 주어진다. ()
입력
첫째 줄에 서강헬스클럽에 비치된 운동기구의 개수를 나타내는 정수
이 주어진다. ()
의 최솟값을 출력한다.
5
1 2 3 4 5
5
PT 첫째 날에 과 를 선택하고, 둘째 날에 와 을 선택하고, 마지막 날에 를 선택하면 은 가 되며, 이때가 이 최소일 때이다.
짧은 버전 기준으로 하겠습니다. (홀수 짝수 따로 처리해주는게 동일)
근손실이 최소가 되게 하려면, 운동 기간 동안 날짜 별로 다른 기구를 이용하면서 가장 큰 근손실이 최소가 되게 해야합니다.
이게 무슨 소리냐면, 1 2 3 4에서 처음과 끝인 1과 4가 아닌 1과 2를 고르면 3과 4만 남게되어 운동 기간동안 얻는 최대 근손실이 7이 되어버립니다. 하지만 1과 4, 2와 3을 고르면 최대 근손실은 5가 되죠.
# 불편한(긴) 버전 - 시간 48 ms
n = int(input())
machines = sorted(list(map(int, input().split()))) # 근손실 정도 오름차순 정렬
ans = 0
if n % 2 == 0: # n이 짝수라면
for i in range(n // 2): # n의 절반까지만 탐색(반대 인덱스도 계산하기 때문)
# 근손실의 합이 최소가 되게 하려면 가장 작은 수와 가장 큰 수를 차례대로 더해주면 됨
ans = max(ans, machines[i] + machines[n - 1 - i])
else: # n이 홀수라면
ans = max(ans, machines.pop()) # 근손실이 가장 큰 기구를 따로 계산
for i in range(n // 2):
# 홀수의 경우 가장 마지막 수를 제외하고 탐색을 하기 때문에 n-2-i를 해줌
ans = max(ans, machines[i] + machines[n - 2 - i])
print(ans)
# 편한(짧은) 버전 - 시간 56 ms
n = int(input())
machines = sorted(list(map(int, input().split())))
# 위에서 홀수의 경우 근손실이 가장 큰 기구를 따로 계산하고 n-2-i를 해준 경우를 초기에 계산
ans, m = (0, n) if n % 2 == 0 else (machines[-1], n - 1)
for i in range(n // 2):
# 초기에 홀짝 여부에 따른 값을 정해주었기 때문에 짝수 홀수 모두 한 줄로 가능
ans = max(ans, machines[i] + machines[m - 1 - i])
# print(ans)