일단 설명하신대로 진행된다면 항상 작은 조각을 선택할테니, 결국 p +1 == q인 부분, 즉 구간의 길이가 2인 부분이 반드시 답으로 나오게 될겁니다.

하지만 질문 게시판에도 나와있는 반례인데, 3 / 2 100 1 에 경우 [0~2]가 가장 작으므로 답은 0이지만, 올려주신 코드는 1을 출력합니다.

0~1 보다 1~2가 작으니 1을 출력하게 되는거죠.

조금 특수한 경우, 즉 k+1 == q일 때를 생각해봅시다. k+1 ~ q인 부분의 평균은 평균이라고 부를 수 있을까요?

쉬운 설명을 위해 p=0, k=1, q=2를 힌트에 대입해보면 다음과 같이 나올겁니다 :

[0~1] <= [0~2] <= [2~2] 또는, [2~2] <= [0~2] <= [0~1]

뭔가 이상하죠. [2~2]는 부분평균에 해당하지 않습니다.

따라서 k+1 == q일때는 [0~1]과 [0~2] 중에 뭐가 더 크고 작은지 알 수 없습니다.

그러므로 k+1==q일때 따로 조건을 만들어 처리해주시면 아마도 AC가 뜨지 않을까 싶습니다.

여기서 조금 더 쉬운 풀이를 생각해보자면, 구간의 길이가 3이라면, 반드시 k+1==q일 수 밖에 없습니다.

따라서 제일 작은 부분평균을 갖는 구간의 길이는 반드시 구간의 길이가 2 또는 3 일때입니다.

구간의 길이가 4 이상이라면 힌트의 부등식에 의해서 반드시 길이가 2~3인 더 작은 부분평균이 존재하니까요.

그래서 단순히 배열에서 인접한 2~3개의 원소의 부분평균만 비교하셔도 이 문제를 해결하실 수 있습니다.