[백준] 20300 서강근육맨 (해설 + 코드)

구현

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

20300번: 서강근육맨

 

코드

import sys 
input = sys.stdin.readline
n = int(input())
w = list(map(int, input().strip().split()))
w.sort()

cost = []
result = 0
if n % 2 == 1:
	for i in range(n//2):
		cost.append(w[i] + w[n-i-2])

	result = max(*cost, w[len(w)-1])
else:
	for i in range(n//2):
		cost.append(w[i] + w[n-i-1])

	result = max(cost)

print(result)

 

설명

"한번 받을때의 근손실 정도가 M을 넘지 않도록하고 싶다"

 

 

1. 우선 조건을 살펴보자면 항상 최대 두개 까지만 선택한다고 한다.
2. 최대 두개니까 하나를 선택할수 도 있다는 말이되며 반드시 2개를 선택하지 않는다고 이해할 수 있다.
3. 이전에 사용하지 않았던 운동기구를 사용하기 때문에 한번 선택한 기구는 다른 기구와 조합할 수 없다.
4. 10개의 운동기구가 있을때 pt를 5번 받으면 모든 기구를 사용할 수 있다.
5. 되도록이면 두개를 사용한다고 했기 때문에 2개를선택하는 방향의 뜻을 이해해보아야 한다.

 

 

"즉 되도록이라는건 될 수 있으면 무조건 2개를 선택한다는 얘기가된다."
"그렇다는건 1회 받을때 2개의 기구를 선택한다는 얘기가 된다."

 

 

 비례식을 세워 확인해보면 1: 2 = x = 10 그렇다면 x = 5회가 되고 5회안에 모든 기구를 사용할 수 있다는 얘기가된다. 만약 9개의 운동기구라면 4..1이기때문에 "2번씩 고른것을 4회하게 되고 마지막 남은 횟수또한 PT횟수로 간주하고 있기 때문에 총 PT횟수는 5회가 된다." 그렇다는건 남은 횟수를 버리지 않고 그대로 사용한다는 의미가된다. 그 근거로 마지막 PT를 받을때는 운동기구를 하나만 사용한다고 한다. (결국 마지막 운동기구 또한 사용한다.) 근손실이 일어나는 정도가 다르고 운동기구마다 근손실의 정도가 다르다고 한다. 근손실의 정도가 "PT를 한번 받을때의 근손실 정도가 M을 넘지 않도록 하고 싶다."

 

 우선 위 문장을 잘 해석해야 되는데 근손실의 정도를 최소로 만들기 위해서는 각기 다른 근손실의 정도가 주어지기 때문에 "해당 근손실의 정도가 작은 것들을 선택하는것이 > 근손실의 정도가 큰것을 선택하는 것 보다 근손실을 줄일 수 있는 방법이된다."  이는 근손실 작은걸 예를들어 1, 2가 있고 9, 10 있다고 해보면 근손실의 정도의 합은 당연히 (1,2)가 작고 (9,10) 더 크기 때문이다. "결국 근손실이 큰 것을 선택하는게 아닌 근손실의 정도가 작은 기구들을 선택해야 결과적으로 근손실의 손실을 줄일 수 있다는 말이된다." 이제 우리가 알고 있는건 "근손실의 정도가 작은 기구들을 선택" 한다는 것이된다. 예제를 보게 되면 근손실의 정도가 5개인 기구가 있기 때문에 총 3회를 받게되고 그중 2회는 2개씩 선택한 기구들을 사용하는 날이 되며 마지막날에는 근손실의 정도가 5인 기구 하나만 사용하게 된다. 자 이제 우리가 고려해야될 점은 두개다.

 

 

근손실이 작은 것들을 조합해본다.
1. (1, 2), (3,4) = 3,7
2. (1, 3), (2,4) = 4,6
3. (1, 4), (2,3) = 5,5

 

 

 그럼 1회 PT마다 근손실의 정도가 어떻게 변화하는지 살펴보자. 이때 우리가 중점적으로 봐야될것은 "최소로 만들어지느냐이다." 그리고 "두개의 기구를 선택해야 된다는 것이다.(2회 pt받는건 되도록 2개를 사용해야 되기 때문이다.)" 첫째날과 둘째날의 관계를 살펴보면 1번 같은 경우 첫째날에는 3정도 둘째날에는 7정도 일어나고 있고둘째날에는 4와 6정도 즉 첫째날에는 7는 무조건 나오게 되고 둘째날에는 6정도는 무조건 나오게된다. 셋째날을 보면 5가 최대로 나올 수 있다.

 

 

"왜 무조건 나오게 되냐 두개의 기구를 선택하는 날이기 때문이다."
"선택할 수 있다면 최대한 2개를 사용해야 되기 때문이다."
그렇다는건 첫번째 경우는 최대 근손실이 7까지나오게 되는것이고

두번째 경우는 최대 6까지 나오게 되는것이며

세번째는 최대 5까지 나오게 되는것이다.

 

 

그럼 7,6,5중에서 가장 작은 5가 "근손실을 최소화 하는 방법" 이라는 뜻이된다.
그 방법을 살펴보면 최대 + 최소의 합을 통해서 만들 수 있는 조합에서 다른 조합으로 만들 수 있는
조합의 큰수들을 막고 있다.

 

 

 "이는 곧 1 번을 통해서 보일 수 있는데 1, 2를 선택하면 가장 작은 기구들을 선택한것이다. 하지만 이후에 있을 근손실의 정도는 다른 조합보다 월등히 크다. 그렇기 때문에 최선의 방법으로 최소의 근손실을 만들기 위한 방법으로는 최대 + 최소로 상한선을 정해두는 것이다. 또한 가장 작은 근손실 정도를 가지고 있는 기구들만 순서대로 선택하는 것은 이후에 있을 근손실을 최소한으로 설정하는 방법이 아니라는 뜻이다." 이 방법을 이용한다면 더 큰 값이 나올 수 있는 경우들을 막아주는 효과를 보일 수 있다. 위와 같은 선택 방법으로 나온 최소한의 값을 마지막 하나의 근손실 정도의 기구와 함께 비교해본다면 "마지막 기구또한 선택해야되는 경우이기 때문에" 본 예제에서는 5로 같기 때문에 이해하기 힘들 수 있지만 만약 10, 19가 존재한다고 했을때 10은 앞에 상황들을 거쳐온 최소한의 값이 되고, 19는 마지막 남은 기구의 근손실 정도라고 볼 수 있다. 

 

 

"그렇다는건 마지막 기구 또한 버리지 않고 선택해야 되기 때문에 결국 19까지는 근손실이 무조건 나올 수 있다는 것이다."

"만약 이를 거부하고 10을 선택하게 된다면 이는 곧 1회 받을때마다 10회를 넘지 않게 한다라는 것에서

19를 선택한다는 경우는 있을 수 없게 된다."

 

 

 우리는 마지막 1회까지도 사용해야되는데 말이다. 그렇기 때문에 최소한의 값이라는건 나올 수 있는 값 중 가장 큰 값을 선택해서

"모든 기구를 다 사용하면서 근손실의 마지노선을 잡게 되는 값이다." 따라서 19를 선택하게 된다면 모든 기구의 조합을 통해서 마지막 기구의 손실정도 까지 고려가 되게 되는 것이고 이는 곧 문제의 부합된다고 생각한다.