https://www.acmicpc.net/problem/20300
No.20300: 서강 근육질의 남자
PT 첫날에 $1$와 $4$를 선택하고 둘째 날에 $2$와 $3$를 선택하고 PT 마지막 날에 $5$를 선택하면 $M$는 $5$가 되며 이는 최소 $ M$.
www.acmicpc.net
문제를 이해하다
- PT 수령 시 운동기구는 최대 2개까지만 선택하실 수 있습니다.
- 나는 이전에 사용하지 않았던 운동기구를 선택할 계획을 세웠다.
- PT를 받을 때 M보다 더 많은 근육이 빠지지 않도록 하고 싶어요.
- 이때 M의 최소값을 구합니다.
- 두 종류의 운동기구로 PT를 받았을 때의 근손실 정도는 두 운동기구의 근육손실 정도를 합산하였다.
문제를 풀다
처음에는 가운데 두 값을 정렬하여 더하면 근솔실의 최소값이 될 것이라고 생각했습니다.
다만, 이는 반복이 없을 경우에 한하며, 반복이 있는 경우에는 카운트하지 않는다.
문제에서 반복을 허용하고 입력을 허용하므로 다음과 같이 풀 수 있다.
- 정렬하여 양쪽 끝에 값을 추가하고 최소값을 업데이트하여 정답을 얻습니다.
- min_lost(최소 근육 손실)는 입력된 근육 손실 목록 길이가 홀수일 때와 짝수일 때 다르게 계산됩니다.
솔루션 코드
n=int(input())
lost=list(map(int, input().split()))
def solution(start, end, lost, min_lost):
while start<end:
temp=lost(start)+lost(end)
if temp > min_lost:
min_lost=temp
start+=1
end-=1
return min_lost
lost.sort()
start, end = 0, n-1
result=-1
if n%2:
min_lost=lost(end)
end-=1
result=solution(start, end, lost, min_lost)
else:
result=solution(start, end, lost, -1)
print(result)