14922. 부분평균

14922번: 부분평균

---

배열 $A$가 주어질 때, 길이가 2 이상인 구간의 평균이 최소인 구간의 시작점의 좌표를 구하는 문제이다.

 

친절하게도 힌트가 나와 있다. $[P,~Q]$ 구간의 부분 평균을 $S(P,~Q)$라고 할 때, $P+1<Q$라면 $P<K<Q$인 정수 $K$에 대해 $S(P,~K) \le S(P,~Q) \le S(K+1,~Q)$ 또는 $S(K+1,~Q) \le S(P,~Q) \le S(P,~K)$가 성립한다. 정리하면 길이가 4 이상인 구간 $[P,~Q]$ 안에 부분평균이 더 작은 서브 구간이 반드시 존재한다는 의미이다.

 

길이가 3인 구간도 $P+1<Q$를 만족하지 않냐고 할 수 있는데, 길이가 3인 구간을 둘로 나누면 둘 중 하나는 길이가 1인 구간이 된다. 길이가 1인 구간은 문제의 부분 평균 조건을 만족하지 않는다.

 

즉, 길이가 2 또는 3인 부분 구간의 평균만 계산하면 된다. 길이가 4 이상인 구간은 볼 필요가 없다. 무조건 더 좋은 답을 찾을 수 있기 때문.

---

힌트가 없었다면 플레급 문제 아닐지..