discuss의 힌트를 보고 쉽게 풀긴 했습니다만 사실 왜 그런지는 이해가 잘 안되네요,,ㅜㅜ 혹시 왜그런지 설명해주실 수 있나요? 아니면 참고할 수 있는 자료도 괜찮습니다,,,
감사합니당
토끼가 최대 m칸 건널 수 있고, m개의 구간합의 최솟값이 ans라고 할 때,
1. ans+1마리는 건널 수 없습니다.
m개의 돌이 있는 구간을 임의로 정했을 때, 토끼는 건널 때 무조건 그 구간에 있는 돌 중 하나를 밟아야만 합니다. 돌이 m개가 연속으로 0이면 절대 건널 수 없으므로 ans마리 이상의 토끼는 건널 수 없습니다.
2. ans마리는 건널 수 있습니다.
m개의 돌이 있는 구간을 임의로 정했을 때, 그 돌의 내구도의 합은 항상 ans 이상입니다. 그러므로 어떤 구간이건 ans마리가 밟을 수 있습니다.
그러므로 답은 ans입니다.
