[백준 15954번] 인형들 (C++)

문제 링크 : https://www.acmicpc.net/problem/15954

#include <bits/stdc++.h>
using namespace std;

int arr[501];
double result = INT_MAX;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int N, K;
    cin >> N >> K;
    for(int i=0; i<N; i++) cin >>arr[i];

    for(int i=K; i<=N; i++) //선택한 인형 수
    {
        for(int j=0; j+i<=N; j++) //선택한 구간
        {
            double sum=0, var=0;
            for(int k=j; k<i+j; k++) //해당 구간 내의 표준 편차
            {
                sum+=arr[k];
            }
            double mean = sum/i; //평균
            for(int k=j; k<i+j; k++)
            {
                var += (arr[k]-mean) * (arr[k]-mean); //편차의 제곱의 합
            }
            var /= i; //분산
            result = min(result, sqrt(var)); //최소 표준 편차
        }
    }

    cout << fixed << setprecision(11) << result;

    return 0;
}

 

최소 K개 이상의 연속된 위치에 있는 인형들을 선택해야 하기에, 첫 반복문 인덱스를 K부터 N까지 설정한다.

그리고 K개 이상의 연속된 구간을 지정해야 하기에 추가적인 반복문으로 구간을 선택해준다. 

이제 마지막 반복문에서 해당 구간에 대해서 표준 편차를 구해준다

.

우선 평균을 구하기 위해 누적합을 구하고, 해당 구간의 인형 개수는 첫 번째 반복문 인덱스 이므로 해당 값으로 나눠 평균을 구한다.

이후 구한 평균을 토대로 편차의 제곱의 합또한 구해주고, 이를 마찬가지로 첫 번째 반복문 인덱스로 나눠준다.

이제 이렇게 구한 값의 제곱근을 구해 오차범위에 주의하여 출력해주면 된다.