[백준 15954] - [카카오 코드 페스티벌 2018 예선] - 인형들 (JAVA)

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

---

이문제는 음 .. 문제를 이해하는데 어렵지는 않았다.

다만 문제를 제대로 읽지 않아 한번 틀렸다. 

그러면서 시간을 30분 정도 더 버린거 같다. 

알고리즘 문제는 대부분 이렇게 시간을 허비하는거 같다.

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

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

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

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

위의 조건으로 문제를 풀어보자.

위의 문장에서 뽑아 내야 하는 문장은 

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

그리고 중요하게 봐야하는 문장이 K개 이상의 연속된 위치 라는 말이다.

저 문장을 제대로 읽지 않고 K개의 연속된 위치로 문제를 풀어서 틀렸다.

문제를 풀기 위해서는 표준 편차를 구해야 한다. 

문제에서 친절하게 표준편차를 구하는 방법을 알려줬다. 

표준 편차를 구하는 방법으로 그대로 표준편차를 구하기 위해 변수들을 정의해보았다.

N개의 수 a1, a2 ~ an 을 int A[] = new int[N] 으로 정의 했다.

K개의 연속된 수는 K 로 정의 했다.

(산술) 평균은 (a1+ a2 + ... + aN) / N 이고 이 값을 m으로 정의 한다고 했으니 나도 m으로 정의 했다. 

표준 편차는 분산의 음이 아닌 제곱근이라고 한다. 그래서 분산은 따로 변수로 두지 않고 바로 제곱근을 구해 표준 편차에 저장했다 

표준 편차의 변수명은 b로 정의 했다. 

여기서 중요하게 봐야 하는 변수는 다른 변수가 아니라 K 이다.

K 개 이상의 연속된 위치라는것은 만약 입력받은 N이 5이고 K가 3이라면 

K는 3, 4, 5 가 될 수 있다는 뜻이다. 

그래서 K가 3, 4, 5 일때 연속된 모든 인형들의 표준 편차를 구해주어야 한다. 

그리고 구해진 표준 편차가 제일 작은 표준 편차를 출력해주면 된다. 

while(K <= N) {  for(int i = 0; i <= N-K; i++) { //m 구하기 double m = getM(A, i, N, K); //b 구하기(표준편차) double b = getB(A, m, i, N, K);   result = Math.min(result, b);  }  K += 1;  }

   

위의 소스처럼 K값이 N과 같을때 까지의 연속된 인형들의 표준 편차를 구했다.

m과 b를 구하는건 식 그대로 구했다.

출력 할때는 예제와 자리수를 같게 하기 위해 자리수가 클 경우 11 자리에서 잘랐다.

오차 범위가 10의 -6승이기에 반올림정도까지는 통과가 되는듯 하다.

자리수를 자르지 않아도 될듯 하긴 한거 같긴한데 시도는 안해봤다.

나머지 문제들도 차근차근 풀어봐야겠다.

이걸 한번에 쉬지 않고 푼 사람들은 실력은 제외하더라도 멘탈과 체력이 얼마나 좋은것일까? 난 이미 바닥 났다. 

나머지는 내일 풀어야지

소스

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
 
public class Main {
 
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
        
        double A[] = new double[N];
        
        st = new StringTokenizer(br.readLine());
        for(int i=0; i < N; i++) {
            A[i] = Double.parseDouble(st.nextToken());
        }
        //입력 완료
        double result = Double.MAX_VALUE;
        while(K <= N) {
            for(int i = 0; i <= N-K; i++) {
                //m 구하기
                double m = getM(A, i, N, K);
 
                //b 구하기(표준편차)
                double b = getB(A, m, i, N, K);
                
                result = Math.min(result, b);
            }
            K += 1;
        }
 
        double newResult = Double.parseDouble(String.format("%.11f", result));
        System.out.println(newResult);
    }
    
    public static double getM (double[] A, int idx, int N, int K) {
        double sum = 0.0;
        for(int i = 0; i < K; i++) {
            sum += A[idx+i];
        }
        return sum / K;
    }
    
    public static double getB(double[] A, double m, int idx, int N, int K) {
        double sum = 0.0;
        for(int i=0; i < K; i++) {
            sum += (Math.pow(A[idx+i]-m, 2));
        }
        return Math.sqrt(sum/K);
    }
}