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

문제 (15954)인형들

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

사용 언어 : JAVA

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

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

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

---

입력 값

• 첫 번째 줄에 N과 K가 주어진다. N은 1 이상 500 이하의 정수이고, K는 1 이상 N 이하의 정수이다.
• 두 번째 줄에는 N개의 정수가 입력되며, 이는 인형이 일렬로 나열된 순서대로 인형을 선호하는 사람의 수이다. 각 수는 모두 106 이하의 음이 아닌 정수이다.

---

출력 값

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

---

내 생각

1. 초기 생각

• 문제 유형을 보니 브루트 포스 유형이길래, 그냥 첫번째 인형부터 K개씩 끊어서 가장 낮은 표준 편자가 되는 집합을 찾고자 했음. 그런데 표준 편차를 구할 때 쓰이는 평균 m을 전체 N개 인형의 선호도 평균인지 K개의 선호도 평균인지 헷갈렸음. 내가 이해한 바로는 그냥 N개의 인형 중에서 가장 인기가 낮은 연속 K개의 인형을 따로 빼준다고 생각해서 당연히 전자의 평균값을 사용해야 하는데 예제 답을 보니 K개의 평균을 사용해야 하길래 뭐지 싶었음.
• 여튼 이중 for문 만들어서 i=0...N-K+1(subList에 담을 첫번째 인형), j=0...K-1(subList 구성용)로 놓고 일일이 표준 편차 구함.
• 근데 안됨!!

2. 개선

일단 첫 알고리즘에서 어느 부분이 문제였지? 생각해 봤는데 진짜 모르겠었음. 뭐가 잘못된건지 문제를 한 글자씩 뜯어 읽었는데,

그 후, 선호하는 사람의 수의 표준편차가 최소가 되는, K개 이상의 연속된 위치에 있는 인형들을 선택하여
표준편차가 최소가 되는, K개 이상의 연속된 위치
K개 이상의 연속된
K개 이상...

진짜 멍청인가봐

그래서 이중 for문의 내부에 for문을 하나가 아니라 두개로 구성, 첫번째 for문은 일단 j=i...K개만큼 subList에 담아 주고 두번째 for문에서 뒤에 하나씩 더 추가하면서 subList의 표준 편차 값을 계속 비교해줌.

그러니까 나는 문제에서 주어진 List의 첫번째 항목부터 시작한 K....N 길이의 subList를 먼저 비교한 뒤에 List의 두번째 항목부터 다시 K...(N-1) 길이의 subList를 비교하는 식으로 했다. 다른 블로그 글을 보니까 그냥 K 길이 짜리 subList를 다 구한 뒤에 K+1개, K+2개... 의 subList를 다시 구성하여 비교하던데 뭐가 더 효율적인진 모르겠다. (크게 상관 없으려나)

그런데!

또 문제가 있었음. 커뮤니티에 올라온 반례 중에 (https://bingorithm.tistory.com/12) 나머지는 다 맞는데
2 2
1 1000000
답: 499999.5
이게 죽어도 안맞았음. 머리 쥐어뜯음.

디버깅 해 보니까, 내가 초반에 min으로 잡아놓은 999999 값이 더 작아서 min = MIN(min, ret) 비교문으로 잡아낼 수가 없었던 것인데.. 구글링 해 보니까 Double.MAX_VALUE 라는 아주 간단하고 좋은 기준이 있길래 냉큼 갖다 썼다.

 

최종 코드

import java.util.Scanner;
import java.lang.*;

public class Main{
    public static void main(String args[]) {
        Scanner input = new Scanner(System.in);
        int N = input.nextInt();
        int K = input.nextInt();
    
        double[] preference = new double[N];
        for(int i=0; i<N; i++) {
            preference[i] = input.nextDouble();
        }

        double minVarience = findMinimum(N, K, preference);

        System.out.println(minVarience);
    }

    public static double findMinimum(int N, int K, double[] list){
        double min = Double.MAX_VALUE;
        int j, k;

        for(int i=0; i<N-K+1; i++){
            double[] subList = new double[N];
            
            for(j=i, k=0; k< K-1; j++, k++){
                subList[k] = list[j];
            }
            for(int l=0; j<N; j++, k++, l++){
                subList[k] = list[j];
                min = MIN(min, getVarience(K+l, subList));
            }
        }

        return Math.sqrt(min);
    }

    public static double MIN(double a, double b){
        if(a>b) return b;
        else    return a;
    }

    public static double getVarience(int K, double[] list){
        double varience = 0;
        double mean = getMean(K, list);

        for(int i=0; i<K; i++){
            varience += Math.pow(list[i]-mean, 2);
        }
        return varience/K;
    }

    public static double getMean(int N, double[] list){
        double mean = 0;

        for(double element : list){
            mean += element;
        }
        mean /= N;
        return mean;
    }
}

 

---

느낀점

• 문제를 "잘" 읽자
• 숫자를 활용한 문제에는 무의식적으로 int에 손이 가는데, 찬찬히 생각해서 자료형 때문에 두번 세번 수정하는 일이 없도록..!ㅠㅠ