Problem :

https://www.acmicpc.net/problem/15954


My Solution :

from decimal import Decimal

N, K = map(int, input().split())
A = list(map(int, input().split()))


def get_min_var(A, K):
sums = [0 for _ in range(N+1)]
sq_sums = sums[:]
for i in range(1, N+1):
sums[i] = sums[i-1] + A[i-1]
sq_sums[i] = sq_sums[i-1] + A[i-1]**2
min_var = Decimal('INF')
for k in range(K, N+1):
for i in range(N-k+1):
m = Decimal(sums[i+k] - sums[i]) / k
var = Decimal(sq_sums[i+k] - sq_sums[i]) / k - m*m
min_var = min(min_var, var)
return min_var.sqrt()


print(get_min_var(A, K))


Comment :

1. K개가 아니라 "K개 이상"임을 주의할 것. 처음에 K개로 풀어서 제출해놓고 왜 틀렸는지 찾아내는데 한참 걸렸다.

2. Python에서 그냥 제출하면 float 정밀도 때문에 오답으로 나온다. decimal.Decimal을 사용해야 정답으로 나온다.

3. Python으로 단순하게 O(N^3)으로 풀면 타임아웃이 발생한다.

4. 이 문제의 핵심은 누적 합을 미리 구해서 구간 합을 바로 계산하는 것과, 누적 합과 누적 제곱 합을 활용해 분산을 O(1)에 바로 구하는 것이다.

secret