백준 온라인 저지의 15954번(카카오 2018 예선) 인형들 문제입니다.
[링크] https://www.acmicpc.net/problem/15954
문제 조건과 설명
- N종류의 인형이 있는데, 그 중 K개 이상의 연속된 위치에 있는 인형들을 선택해 같은 곳에 놓습니다.
- 단, K개 이상의 연속된 인형들을 선택했을 때, 선택된 인형들을 선호하는 사람의 수의 표준편차 값이 최소가 되어야 합니다.
- 즉 위 조건을 만족하도록 K개 이상의 연속된 인형들을 선택해야 하며, 최소가 될 때의 그 표준편차를 출력하는 문제입니다.
Input
첫 번째 줄에 N과 K가 주어집니다. N은 1 이상 500 이하의 정수이고, K는 1 이상 N 이하의 정수입니다.
두 번째 줄에는 N개의 정수가 입력되며, 이는 인형이 일렬로 나열된 순서대로 인형을 선호하는 사람의 수 입니다. (모든 수는 10^6 이하의 음이 아닌 정수)
Output
K개 이상 선택된 인형들을 선호하는 사람의 수의 표준 편차를 출력합니다.
생각한 아이디어
첫 번째 인형부터 K개만큼 연속으로 선택한 인형까지, 선호하는 사람 수의 표준편차를 구합니다.
그 다음은 두 번째 인형부터 K개만큼 연속으로 선택한 인형까지, 선호하는 사람 수의 표준편차를 구합니다.
이렇게 계속하여 K개만큼 선택할 수 있을 때까지 반복 계산합니다.
K개 이상 선택해야 하므로, 연속된 K개만큼 선택하는 모든 경우의 수를 진행한 후에는 다시 K+1개만큼 선택하는 것으로 진행합니다.
그 다음은 K+2개만큼 진행하고, 이것을 N 이하가 될 때까지, 즉 모든 인형들을 다 선택하는 경우가 올 때까지 K값을 증가시키며 반복 계산하여 줍니다.
예를 들어 인형이 5개가 있고, K가 3이었다면,
- 1,2,3번째 선택 후 계산 -> 2,3,4번째 선택 후 계산 -> 3,4,5번째 선택 후 계산 -> 4,5,6 을 하려 했지만 6번째 인형은 없으므로 계산 종료 -> K값 1 증가 = 4
- 1,2,3,4번째 선택 후 계산 -> 2,3,4,5번째 선택 후 계산 -> 3,4,5,6은 안되므로 종료 -> K값 1 증가 = 5
- 1,2,3,4,5번째 선택 후 계산 -> 이후 K값이 인형의 종류 갯수 N과 같기 때문에, K값을 더 늘려 인형의 종류보다 많이 선택할 수는 없으므로 종료한다.
소스코드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
#include <iostream>
#include <cstdio>
#include <vector>
#include <algorithm>
#include <cmath>
using namespace std;
int main() {
vector <double> v;
int N, K, tempK;
int idx = 0;
double input;
double sum = 0, m = 0;
double var = 0, sd = 0;
double minSd = 9999999999999;
scanf("%d %d", &N, &K);
for (int i = 0; i < N; i++) {
scanf("%lf", &input);
v.push_back(input);
}
tempK = K;
while (tempK <= N) { // K값이 N 이하일 때까지 반복
if (idx + tempK - 1 <= N - 1) {
for (int j = idx; j < idx + tempK; j++) {
sum += v[j];
}
///// 계산 부분 /////
// 평균 계산
m = sum / (double)tempK;
// 표준편차 계산
for (int j = idx; j < idx + tempK; j++) {
var = var + (v[j] - m) * (v[j] - m);
}
var = var / (double)tempK;
sd = sqrt(var);
/////////////////
// 최소값 판단하기 //
if (minSd > sd)
minSd = sd;
sum = 0; var = 0;
idx += 1;
}
else {
idx = 0;
tempK += 1;
}
}
printf("%.6lf", minSd);
}