[BOJ] 15954:인형들

0. 문제

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

15954번: 인형들

 

1. 문제분석

- 주어진 최소 개수 이상의 크기 만큼 순차적으로 표본집합을 만들어 분산 및 표준편차 값을 구하는 비교적 단순한 브루트 포스(Brute Force) 문제이다.

 

2. 주의할 점

- 값이 double 또는 float으로 이루어지다 보니, 소수점 이하의 값이 처리 도중 잘못 바뀌는 상황에 유의하며 문제를 풀어야 한다. 특히 위 수식 중 두번째 수식처럼 곱하기, 나누기의 연산이 더 빈번히 일어나는 경우는 가급적 피한다.

- 지문이 길다. 문제를 잘 읽어야 한다.

- 표본집합의 크기를 먼저 정하고, 그 다음 어떤 표본을 고를지를 선택한다.

 

 

3. 소스코드(Java)

// boj 15954 인형들

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;

public class boj_15954 {
    static int n, k;
    static double ans = 999999999;
    static int[] ppl;

    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());

        n = stoi(st.nextToken());
        k = stoi(st.nextToken());
        ppl = new int[n];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < n; ++i) ppl[i] = stoi(st.nextToken());
        for (int size = k; size <= n; ++size) {
            for (int i = 0; i <= n - size; ++i) {
                double tmp = sigma(Arrays.copyOfRange(ppl, i, i + size));
                ans = Math.min(ans, tmp);
            }
        }
        System.out.print(ans);
    }
    static int stoi(String s) {return Integer.parseInt(s);}
    static double sigma(int[] subArray) {
//        int size = subArray.length;
//        double eOfNsq = 0, eSqOfN = 0;
//        for (int now : subArray) {
//            eOfNsq += (double) now * now;
//            eSqOfN += (double) now;
//        }
//        eOfNsq /= (double) size;
//        eSqOfN /= (double) size;
//        eSqOfN = eSqOfN * eSqOfN;
//        return Math.sqrt(eOfNsq - eSqOfN);
        double size = subArray.length;
        double avg = 0, var = 0;
        for (int now : subArray) avg += now;
        avg /= size;
        for (int now : subArray) var += (now - avg) * (now - avg);
        var /= size;
        return Math.sqrt(var);
    }
}

 

4. 여담

- 소숫점이 들어가는 문제는 언제나 개빡친다............

- 카카오 2018 코드페스티발 예선 문제. 그때는 풀다가 포기했던 문제다..ㅎㅎ