[백준] 15954 - 인형들

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

15954번: 인형들

 

작년도 카카오 코드 페스티벌에 출제되었던 문제. 당시에 참가했을 때는 못풀었었다...

 

주어진 조건에서 편차의 최솟값을 구하는 문제이나 두 가지 유의할 점이 있다.

 

1. 소수의 정밀도

  일반적인 c++ float, double, python의 float type을 사용하는 경우 부동 소수점 형의 오차로 인해 정답을 구하기 어렵다고 한다. 따라서 c++의 경우 long double 타입을 (%Lf), python의 경우 decimal.Decimal() 클래스를 사용한다.

 

2. 시간 복잡도

  각 조건에 맞는 인형 그룹에 대하여 각각 평균과 편차를 계산할 경우 O(N^3)의 시간복잡도를 갖는다. 해당 문제의 경우 시간복잡도를 O(n^2)까지 줄여야 한다.

 

  평균의 경우, 합계를 구할 때, 그룹을 변경할 때마다 구하지 않고 이전 구간의 합계에 추가하여 구하면 O(1) 로 평균을 구할 수 있다.

  표준편차의 경우, 각 인형에서의 편차를 계산하는 방식(O(n))을 사용하지 않는다. 분산 내부의 제곱항들을 모두 푼 뒤, 정리하면 각 인형의 선호수의 '제곱의 평균'과 평균에 관한 식으로 정리할 수 있다. 제곱의 평균은 앞서 평균을 계산한 것과 같이 O(1)이므로 표준편차의 계산 역시 O(1)의 복잡도로 해결할 수 있다.

 

<Python 코드>

import sys
import math
from decimal import *
 
getcontext().prec = 28
lines = sys.stdin.readlines()
n, k = tuple(map(int, lines[0].split()))
arr = list(map(Decimal, lines[1].split()))
re = Decimal('inf')
 
# 시작점 변경
for s in range(n-k+1):
    sum_val = sum(arr[s:s+k-1])
    sum_val_sq = sum([v*v for v in arr[s:s+k-1]])
 
    # 길이 변경
    for l in range(k, n-s+1):
        sum_val += arr[s+l-1]
        sum_val_sq += arr[s+l-1] ** 2
        aver = sum_val / Decimal(l)
        std = (sum_val_sq / Decimal(l) - aver ** 2).sqrt()
 
        re = min(re, std)
 
print(re)