[백준] 인형들

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

15954번: 인형들

 

K 이상의 연속된 인형의 값의 표준편차 중 가장 작은 값을 반환하면 되는 문제다.

반목문을 통하여 구한 K 이상의 길이의 배열들의 표준편차를 구할 때 필요한 평균 또는 분산의 값들은 누적 합을 통하여 새로이 정의된 배열을 통해서 구한다. (시간 초과 방지)

 

sumDolls[][0] 은 누적 합이며, sumDolls[][1] 은 누적 제곱합이다.

m(평균) = (sumDolls[end][0] - sumDolls[start][0]) / (end - start)(= k)

v(분산) =

(v1 - m)^2 + (v2 - m)^2 + ... + (vk - m)^2 = v1^2 * v2^2 * ... * vk^2 - 2 * (v1 + v2 + ... + vk) * m + k * m^2

=

sumDolls[end][1] - sumDolls[start][1] - 2 * (m * k) * m + k * m^2

=

sumDolls[end][1] - sumDolls[start][1] - k * m^2

 

상대/절대 오차를 고려하여 python 에서는 float 형이 아닌  decimal.Decimal 을 이용한다.

 

import sys, math
from decimal import Decimal

N, K = map(int, sys.stdin.readline().split())
dolls = list(map(Decimal, sys.stdin.readline().split()))
answer = Decimal('inf')
e1, e2 = 0, 0
sumDolls = []

for i in dolls:
    e1 += i
    e2 += (i * i)
    sumDolls.append((e1, e2))

for k in range(K, N+1):
    for i in range(N-k+1):
        m = (sumDolls[k+i-1][0] - (sumDolls[i-1][0] if i-1 >= 0 else 0)) / Decimal(k)
        v2 = sumDolls[k+i-1][1] - (sumDolls[i-1][1] if i-1 >= 0 else 0)
        answer = min(math.sqrt((v2 - (m * k * m)) / Decimal(k)), answer)

print(answer)