"또한, 각각의 마나 수정들 사이의 강도 순서가 어떤 지도 이미 알고 있다!" 문장에서 나와 있듯이, 어떤 수정이 응집된 마나 수정인지 정확히 압니다.
그리고 최악의 경우, 다른 수정을 내리치는건 응집된 마나 수정의 강도를 알아내는데는 별 쓸모가 없을수 있습니다 (N - K개의 수정의 강도가 0에 한없이 가깝고, K - 1개의 수정의 강도가 P에 한없이 가까울수 있음)
그러면 N하고 K는 문제에 필요없는 입력값이 되고, 응집된 마나 수정에만 망치를 내리친다고 가정해봅니다.
또 조금 더 생각해보면, (0, W] 구간 안에 있는 힘으로 적어도 한번의 망치를 내리쳐야 한다는걸 알 수 있습니다 (가장 작은 힘으로 내리친게 p > W라고 한다면, 응집된 마나 수정의 강도가 p - W 이하인 경우를 생각해보세요)
비슷한 논리로 (W, 2W] 구간, (2W, 3W] 구간 ..., 다 한번씩은 내리쳐야 합니다.
즉 필요한 최소 횟수는 ceil(P / W)가 됩니다. 그리고 이 횟수가 충분하다는것도 쉽게 알 수 있죠.
zizon233 5년 전
이런식으로 짜봤는데... 고민해도 답이 안나오네요.