[백준 15954] 인형들

www.acmicpc.net/problem/15954

15954번: 인형들

from decimal import Decimal


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

sums = [0 for i in range(N+1)]
exps = [0 for i in range(N+1)]

for i in range(1, len(arr)+1):
    sums[i] = sums[i-1] + arr[i-1]
    exps[i] = exps[i-1] + arr[i-1] ** 2

re = Decimal('INF')

for i in range(K, N+1): # 즉 개수.
    for j in range(N-i+1):
        mean = Decimal(sums[i+j] - sums[j]) / i
        var = Decimal(exps[i+j] - exps[j]) / i - mean * mean
        re = min(re, var)

print(re.sqrt())

풀이

먼저 분산을 구하는 식을 알아야 한다.

분산은 식을 정리하면

분산 = 제곱의 평균 - 평균의 제곱이다.

고등학교때 배웠지만 나는 이 공식을 까먹어서 시간초과가 나 풀이를 참고했다.

 

제곱의 평균, 평균 둘다 누적합을 통해 빠르게 구할 수 있다.

구한것을 토대로 표준편차를 구하고 최솟값을 비교해 주면 된다.

 

참고 : 분산공식 유도

 

시간복잡도

O(N2)으로 풀기위해서는 누적합을 필수적으로 써야한다.

누적합을 이용해서 평균과 분산을 O(1)로 구한다.

평균과 분산을 O(N^2)번 구해야 하기 때문에 총 시간복잡도는 O(N^2) 이다.