[Python3] 카카오 코드 페스티벌 2018 예선 - 인형들
2019.01.18 01:30
|
프로그래밍
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)에 바로 구하는 것이다.
'프로그래밍' 카테고리의 다른 글
| [Python3] 카카오 코드 페스티벌 2018 예선 - 인형들 (0) | 2019.01.18 |
|---|---|
| [LeetCode][Python3] 230. Kth Smallest Element in a BST (0) | 2019.01.15 |
| [LeetCode][Python3] 454. 4Sum II (1) | 2019.01.13 |
| [LeetCode][Python3] 78. Subsets (0) | 2019.01.13 |
| [LeetCode][Python3] 238. Product of Array Except Self (0) | 2019.01.12 |
| [LeetCode][Python3] 347. Top K Frequent Elements (0) | 2019.01.05 |
| [LeetCode][Python3] 94. Binary Tree Inorder Traversal (1) | 2019.01.03 |
| python-ldap Windows Active Directory unicodePwd userAccountControl DSID-031A120C (0) | 2018.12.20 |
| [LeetCode][Python3] 62. Unique Paths (6) | 2018.11.15 |
