-
문제 링크
-
사용 언어
C++
-
소스
#include <iostream> using namespace std; int N; int A[1000000]; double Min = 700000000; int Index = 0; int main() { cin >> N; for(int i = 0; i < N; i++) cin >> A[i]; for(int i = 0; i < N-1; i++) { double Avg = (A[i] + A[i+1])/2; if(Avg < Min){ Min = Avg; Index = i; } } for(int i = 0; i < N-2; i++){ double Avg = (A[i] + A[i+1] + A[i+2])/3; if(Avg < Min){ Min = Avg; Index = i; } } cout << Index; } -
논리
우선 문제에서 정의한 대로 부분평균 A(i, j)를 정의하겠다.
문제 해결을 위한 가장 간단한 아이디어는 모든 i, j에 대해 A(i, j)를 계산하고
그 중 가장 작은 A(i, j)를 찾는 것이다.
하지만 이 방법의 시간복잡도는 O(N2)이며, 시간초과에러를 만나게 된다.
몇 개의 예시를 계산해본 결과 다음과 같은 통찰에 달할 수 있었다.
최소가 되는 부분평균을 찾기 위해서는 연속된 2개 또는 3개의 값만 조사해도 충분하다는 것이다.
그렇다면 정말 그러한지 증명해보도록 하자.
-
def : \(A\left[i,j\right] = \left\{ a_i, a_{i+1}, ..., a_j \right\}, \quad A(i,j) = \frac{\sum_{k=i}^j a_k}{j-i+1}\)
-
claim : \(\forall A,\ \exists u,v\quad s.t\quad [\; \left|u-v\right|\le2\quad\land\quad\forall i,j\quad A(u,v)\le A(i,j) \; ]\)
-
proof : 수학적 귀납법을 사용하여 증명하도록 하겠다.
다음은 분명 참이다.
\[\forall A \quad (|A|=3),\ \exists u,v\quad s.t\quad [\; \left|u-v\right|\le2\quad\land\quad\forall i,j\quad A(u,v)\le A(i,j) \; ]\]자, 그럼 아래와 같이 가정하자.
\[\forall A \quad (|A|=k),\ \exists u,v\quad s.t\quad [\; \left|u-v\right|\le2\quad\land\quad\forall i,j\quad A(u,v)\le A(i,j) \; ]\]이 때, 아래 내용이 참이면 임의의 A에 대해 참임이 증명된다.
\[\forall A \quad (|A|=k+1),\ \exists u,v\quad s.t\quad [\; \left|u-v\right|\le2\quad\land\quad\forall i,j\quad A(u,v)\le A(i,j) \; ]\]결론부터 말하면, A의 최소부분평균이 되는 부분배열 m은
\(A[1,k]\) 또는 \(A[2, k+1]\)에 속해 있다는 것이다.
특히, \(k=|A[1,k]|=|A[2,k+1]|\) 이므로, m의 길이는 3이하이다.
일단, 다음은 분명 참이다.
\[|A|=N \quad \Rightarrow \quad A(1, N) \ge \mbox{min}(A(1,N-2),\;A(N-1,N),\;A(1,2),\;A(3, N))\]왜냐하면 아래와 같이 설명할 수 있다.
\[\begin{cases} A=\{a_1, a_2, ..., a_N \},\\ \\A(1,N)=m,\\ \\a_i=m+b_i \end{cases}\]그러면
\[b_1 + b_2 + ... + b_N = 0\]이다.
그러면
\[\begin{cases} A(1, N-1) = m + \frac{b_1 + b_2 + ... + b_{N-2}}{N-2} = m - \frac{b_{N-1} + b_N}{N-2}\\ \\ A(N-1, N) = m + \frac{b_{N-1} + b_{N}}{2} \end{cases}\]이므로
\[\begin{cases} A(1, N-2) > m \quad \Rightarrow \quad A(N-1, N) < m \\ \\ A(N-1, N) > m \quad \Rightarrow \quad A(1, N-2) < m \end{cases}\]임을 알 수 있다.
마찬가지로
\[\begin{cases} A(1, 2) > m \quad \Rightarrow \quad A(3, N) < m \\ \\ A(3, N) > m \quad \Rightarrow \quad A(1, 2) < m \end{cases}\]이다.
또한
\[\begin{cases} A[1,N-2] \subset A[1,N-1] \\ \\ A[N-1,N] \subset A[2,N] \\ \\ A[1,2] \subset A[1,N-1] \\ \\ A[3,N] \subset A[2,N] \end{cases}\]이므로, A의 최소가 되는 부분배열은 \(A[1,N-1], \; A[2,N]\) 에서만 찾으면 되는 것이다.
이로써 증명이 완료 됐지만, 의문이 남을 수도 있다.
사실 부분배열의 길이가 2인 것에 대해서만 찾아도 되는 것 아닐까?
즉, claim을 아래와 같이 선언해도 되지 않을까?
\[\forall A,\ \exists u,v\quad s.t\quad [\; \left|u-v\right|\le1\quad\land\quad\forall i,j\quad A(u,v)\le A(i,j) \; ]\]이 부분은 금세 반례를 들어 부정할 수 있다.
A = {1, 100, 2} 인 경우를 살펴보자.
금세 답이 나올 것이다.
-