2435번 기상청 인턴 신현수

연속된 k개를 더하여 합을 구하되, 최소인 것을 출력하는 문제입니다.

단순하게 i마다 [n - k - 1 + i, n - 1 + i] 구간의 합을 구하여 그 중 최솟값을 구해도 되겠지만 (n <= 100) 앞쪽부터 부분합을 구하여 놓는 아이디어를 떠올려 빠르게 계산할 수 있습니다.

요컨대, 온도의 배열 T가 있다면 부분합의 배열 S는 다음과 같이 정의할 수 있습니다.

S[i] = T[0] + T[1] + ... + T[i]

그러면 A[i]부터 k개의 합은 다음과 같이 표현할 수 있습니다.

S[i + k - 1] - S[i - 1]

이 값의 최소를 구하는 것은 O(n)에 달성할 수 있습니다.