[BOJ] 백준 15954번 : 인형들 (JAVA)

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

15954번: 인형들

문제

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

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

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

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

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

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

 

풀이

브루트포스와 수학적 지식을 활용하면 쉽게 풀 수 있는 문제였습니다. 사실상 여기서 말하는 수학적 지식도 평균과 분산, 표준편차에 해당하는데, 위에서 식을 다 주었기때문에 그대로 이용하면 됩니다. 다만, 연속된 K개가 아니라 연속된 K개 이상(N 이하)라는 점을 잘 캐치해야 했습니다.

제가 푼 로직은 아래와 같습니다.

1. 시작점과 K를 인자로 넘겨주어, 평균을 구한다.

2. 시작점과 K, 평균을 인자로 넘겨주어, 표준편차를 구한다.

3. K > N일 때까지, 모든 경우를 브루트포스하면서 최소 표준편차를 구해 준다.

 

여기서 주의할 점은 소수점을 11자리까지 표시해야한다는 것입니다. 예제를 보면, 2개 모두 소수점 이하 11자리까지 표시했기때문에 우리도 이에 맞춰서 출력해 주어야합니다.

방식은 String.format(".%.11f", ans)를 이용하는 것인데, 2번째 인자는 double 타입으로 넘겨주면 됩니다. 다만, 소수점 12번째 자리에서 반올림을 해서 11번째 자리로 만드는 것이기때문에 오차가 일어나지 않을까 걱정했는데, 문제에서 10^-6이하 상대오차까지는 허용한다고해서 상관없었습니다.

 

아래는 위 로직을 구현한 소스코드입니다.

 

소스코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.StringTokenizer;
 
public class Main {
 
    public static void main(String[] args) throws Exception {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int N = Integer.parseInt(st.nextToken());
        int K = Integer.parseInt(st.nextToken());
 
        int[] arr = new int[N];
        st = new StringTokenizer(br.readLine());
        for (int i = 0; i < N; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }
 
        double ans = Double.MAX_VALUE;
        double ret = 0;
 
        for (int i = K; i <= N; i++) {
            for (int j = 0; j <= N - i; j++) {
                double m = mean(arr, j, i);
                ret = standardDeviation(arr, m, j, i);
                ans = Math.min(ans, ret);
            }
        }
 
        bw.write(String.format("%.11f", ans)+ "\n");
        bw.flush();
        bw.close();
        br.close();
    }
    
    // 평균을 구하는 함수
    public static double mean(int[] arr, int start, int K) {
        double sum = 0.0;
        for (int i = 0; i < K; i++) {
            sum += arr[start + i];
        }
        return sum / K;
    }
    
    // 표준 편차를 구하는 함수
    public static double standardDeviation(int[] arr, double m, int start, int K) {
        double sum = 0.0;
        for (int i = 0; i < K; i++) {
            sum += Math.pow(arr[start + i] - m, 2);
        }
        return Math.sqrt(sum / K);
    }
 
}

 

지적 혹은 조언 환영합니다! 언제든지 댓글로 남겨주세요.