시간 초과
2년 전의 나.. 소스코드를 봤더니 문제 이해도 제대로 못하고 무작정 제출만 했던 것 같습니다. ㅠㅠ
틀렸습니다
2년 전의 저를 믿고 pypy3로 제출했더니 역시나 오답 ㅎㅎ 소스를 아예 갈아엎고 다시 시작합니다.
문제 이해를 하고 다시 접근해 풀었습니다.
문제 설명
단순 브루트포싱 문제입니다. 페이지에 문제 설명이 꽤 길지만 요약하자면
- 총 N개의 인형, K개 이상의 인형을 선택해야 한다. (즉, K의 크기가 N까지 커질 수 있다는 뜻)
이게 무슨 말이냐면 우선, 첫 번째 예제 입력을 적용했을 때 선택되는 범위는 아래와 같습니다.
범위를 벗어나지 않는 선에서 O(n2)의 반복문을 돌려 접근합니다.
- 1,2,3
- 1,2,3,4
- 1,2,3,4,5
- 2,3,4
- 2,3,4,5
- 3,4,5
그리고 중요한 것이 처음에 입력된 배열의 전체 평균이 아니라 선택되는 만큼의 평균, 분산, 표준편차가 쓰입니다!!
평균 : 선택된 범위의 합 / 선택된 범위의 개수
분산 : (선택된 범위의 요소 - 평균)2 의 합
표준편차 : 분산의 제곱근(루트)
용어에 대한 계산 방식은 문제에 잘 나와 있습니다.
여기까지 왔다면 반복문을 통해 어렵지 않게 구현이 가능할 것입니다.
소스 코드
math는 sqrt(제곱근)을 위해 선언되었습니다.
가장 어려웠던 게 반복문의 범위 지정이었습니다.
선택된 범위 내에서 산술평균을 구하고 분산을 반환하는 함수 sdFunc
어차피 모든 값들에 제곱근이 씌워질 것이므로 대소 비교하는 단계에서는 분산까지만 계산합니다.
[순서] 산술평균 - 분산 - 대소 비교 - 표준편차
여기까지만 계산해도 대소 비교는 동일한 결과이므로 가장 작은(min) 값을 제곱근 연산 후 출력합니다.
##########################################################
import sys
from collections import deque
direction = [[0,1],[-1,0],[1,0],[0,-1]] #for BFS
input = sys.stdin.readline
def ip():return input().rstrip()
def lip():return list(ip())
def ips():return ip().split()
def ii():return int(input())
def mii():return map(int,ips())
def lmii():return list(mii())
##########################################################
import math
n,k = mii()
arr = lmii()
def sdFunc(target):
dis = 0
avg = sum(target)/len(target)#산술평균
for z in target:
dis+=(z-avg)**2
return dis/len(target)#분산 반환
answer = list()
for i in range(n-k+1):#K개 이상의 = n-k
for j in range(n-k-i+1):#해당 범위로 리스트를 훑음
tmp = arr[i:i+k+j]
a = sdFunc(tmp)
answer.append(a)
print(math.sqrt(min(answer)))