[백준] 15954 - 인형들
https://www.acmicpc.net/problem/15954
15954번: 인형들
첫 번째부터 세 번째까지의 인형을 선택하면 표준편차는 2/3의 양의 제곱근이 되고, 이 때 표준편차가 최소가 된다. 두 번째부터 네 번째까지의 인형을 선택하는 경우와, 세 번째부터 다섯 번째까지의 인형을 선택하는 경우에도 값은 같다.
www.acmicpc.net
작년도 카카오 코드 페스티벌에 출제되었던 문제. 당시에 참가했을 때는 못풀었었다...
주어진 조건에서 편차의 최솟값을 구하는 문제이나 두 가지 유의할 점이 있다.
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 코드>
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
|
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)
|
cs |