세상에는 마법을 쓸 수 있는 이상한 박사와 엄청난 재산을 가진 강철 남자가 있다. 이상한 박사는 바위가 있는데, 이 바위를 농부 타씨가 가져가려고 한다. 이상한 박사는 온 힘을 다해서 바위를 지켰다. 강철남자도 이상한 박사를 도와서 바위를 지켰다. 그런데, 농부 타씨의 손에서 빛이 나더니, 갑자기 이상한 박사가 농부 타씨에게 바위를 건네주었다. 그리고 나서 강철 남자에게 하는 말이.... 이제는 가망이 없어.... 강철남자는 이 골때리는 이상한 박사에게 응징을 하려고 한다. 이상한 박사는 강철남자가 자신에게 응징을 하려면 다음 문제를 풀어야 한다고 한다. 이상한 박사에게 응징을 하기 위해 이 문제를 풀어주자. <----여기까지의 내용은 문제 해결과 관련이 없으므로, 빠른 문제 해결을 원하시는 분은 안 읽으셔도 됩니다----> 바위 N개가 일렬로 나열된 장식물이 있다. 각 바위의 크기는 A_i(1 <= i <= N)이다. 강철 남자는 자신의 재산 1억원을 이용해서 바위 1개의 크기를 1 줄일 수 있다. 단, 크기가 1이상인 바위의 크기는 줄일 수 있지만, 0인 바위의 크기를 줄일 수는 없다. 강철남자의 재산은 M억원이다. 강철남자는 응징을 하기 위해 불타있으므로, M억원까지 재산을 다 사용할 수 있다. 물론 재산을 사용하지 않을 수도 있다. 당신은 인접한 바위의 크기의 차이의 최댓값의 최솟값을 구해야 한다. 즉, A_i를 1 줄이는 연산을 최대 M번 실행했을 때, max(|A₂ - A₁|, |A₃ - A₂|, ... , |A_N - A_{(N - 1)}|)의 최솟값을 구해야 한다. 이상한 박사의 응징을 위해서 위의 문제를 해결해주자.

가망이 없다고? #2

문제 설명

입력

출력

예제

코드 제출

로그인

LOGIN