zizon233   5년 전

이런식으로 짜봤는데... 고민해도 답이 안나오네요.

solveit   5년 전

"또한, 각각의 마나 수정들 사이의 강도 순서가 어떤 지도 이미 알고 있다!" 문장에서 나와 있듯이, 어떤 수정이 응집된 마나 수정인지 정확히 압니다.

그리고 최악의 경우, 다른 수정을 내리치는건 응집된 마나 수정의 강도를 알아내는데는 별 쓸모가 없을수 있습니다 (N - K개의 수정의 강도가 0에 한없이 가깝고, K - 1개의 수정의 강도가 P에 한없이 가까울수 있음) 

그러면 N하고 K는 문제에 필요없는 입력값이 되고, 응집된 마나 수정에만 망치를 내리친다고 가정해봅니다.

또 조금 더 생각해보면, (0, W] 구간 안에 있는 힘으로 적어도 한번의 망치를 내리쳐야 한다는걸 알 수 있습니다 (가장 작은 힘으로 내리친게 p > W라고 한다면, 응집된 마나 수정의 강도가 p - W 이하인 경우를 생각해보세요)

비슷한 논리로 (W, 2W] 구간, (2W, 3W] 구간 ..., 다 한번씩은 내리쳐야 합니다. 

즉 필요한 최소 횟수는 ceil(P / W)가 됩니다. 그리고 이 횟수가 충분하다는것도 쉽게 알 수 있죠.

zizon233   5년 전

설명 잘 들었습니다. 그런데 의문점이 드는게 하나있어요.

예를 들어 입력값이 3 1 18 4 라면 값은 5가 되야 정답이죠. 그런데 뒤에 2개의 값이 있어서 1과 2는 응집된 마나 수정이 아닐거란말이죠. 그러면 3부터 18까지만 체크를 하면되기때문에 4가 정답이 될거라 생각하는데 어떻게 생각하세요?

zizon233   5년 전

아 강도가 정수가 아닐거란 생각을 못했네요. 대단하십니다.

댓글을 작성하려면 로그인해야 합니다.