문제 설명

카카오프렌즈 스토어에서는 N종류의 인형을 팔고 있다. N개의 인형들 중에서는 잘 팔리는 인형과 그렇지 않은 인형들이 섞여 있어서 잘 팔리는 인형은 상대적으로 사람들이 많이 볼 수 있는 곳에 배치하고, 잘 팔리지 않는 인형은 상대적으로 사람들이 적게 볼 수 있는 곳에 배치한다. 그러므로 배치된 곳이 가까운 두 인형은 상대적으로 판매량이 비슷하다고 할 수 있다.

좋은 배치를 정하기 위해서 어느 날, 여러 명의 사람들을 대상으로 인형의 선호도를 조사하였다. 조사 결과 각 인형에 대해서 선호하는 사람의 수를 모두 구하였고, 그에 따라 인형의 배치를 정하려고 한다.

카카오프렌즈 스토어를 관리하는 브라이언은 어떠한 특정한 곳에 인형들을 배치하고자 하는데, 그곳에 인형들을 선택하는 방법은 다음과 같다:

  • 먼저 비슷한 인형이 가깝게 위치하도록 서로 다른 N개의 인형을 종류당 한 개씩 일렬로 배치한다.
  • 그 후, 선호하는 사람의 수의 표준편차가 최소가 되는, K개 이상의 연속된 위치에 있는 인형들을 선택하여 그들을 같은 곳에 배치한다.

위의 방법으로 인형들을 선택했을 때, 선택된 인형들의 선호하는 사람의 수의 표준편차를 구하여라.

N개의 수 a1, a2, …, aN이 주어져 있을 때, 통계학에서 (산술) 평균은 (a1 + a2 + … + aN) / N 으로 정의한다. 이를 m으로 정의하자. 또한, 분산은 ((a1 - m)^2 + (a2 - m)^2 + … + (aN - m)^2) / N으로 정의하고, 표준 편차는 분산의 음이 아닌 제곱근으로 정의한다.

입력

첫 번째 줄에 N과 K가 주어진다. N은 1 이상 500 이하의 정수이고, K는 1 이상 N 이하의 정수이다.

두 번째 줄에는 N개의 정수가 입력되며, 이는 인형이 일렬로 나열된 순서대로 인형을 선호하는 사람의 수이다. 각 수는 모두 106 이하의 음이 아닌 정수이다.

출력

선택된 인형들을 선호하는 사람의 수의 표준 편차를 출력한다. 출력한 결과와 실제 답을 비교하였을 때의 상대/절대 오차가 10-6 이하인 경우에만 정답으로 인정한다.

입출력 예 설명

예제 입력#1

5 3
1 2 3 4 5

예제 출력#1

0.81649658092

예제 입력#2

10 3
1 4 1 5 9 2 6 5 3 5

예지 출력#3

0.94280904158

문제 풀이

연속된 K개의 경우만 구했더니 오답이였다.

K개부터 시작해서 K개 이상의 표준편차까지 구해주어야 했었다.

import Foundation


func getStandardDeviation(_ k: Int, _ list:[Double]) -> Double {
    let average = list.reduce(Double(0)){$0 + $1} / Double(k)
    
    let variane = list.map{pow($0-average, 2)}.reduce(Double(0)) { $0 + $1 } / Double(k)
    let standardDeviation = sqrt(variane)
    
//    print("List:\(list)")
//    print("average: \(average) variance: \(variane) standard:\(standardDeviation)")
    return standardDeviation
}

func getMinimumStandardDeviation(_ n: Int, _ k: Int, _ list: [Double]) -> Double{
    var startDoll = 0
    var standardDeviationList : [Double] = []
    
    while startDoll + k != n + 1{
        var K = k
        
        while K + startDoll < n + 1 {
            let nList = list[startDoll...startDoll+K-1]
            standardDeviationList.append(getStandardDeviation(K, Array(nList)))
            K+=1
        }
        startDoll += 1
    }
    
    return standardDeviationList.min()!
}

let nk = readLine()!.components(separatedBy: " ").map { Int($0)! }
let list = readLine()!.components(separatedBy: " ").map { Double($0)! }


let standardDeviation = getMinimumStandardDeviation(nk[0], nk[1], list)
print(standardDeviation)

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