[Python3] 카카오 코드 페스티벌 2018 예선 - 인형들

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)에 바로 구하는 것이다.