백준 15954번 문제 풀기

문제 링크

처음에는 수열의 부분합의 최소를 구하는 문제의 변형인거 같아서 다양한 최적화 방법을 생각해 봤는데 분산을 구할때 시간 복잡도를 낮추는 방법을 생각해내지 못해서 N이 최대 500이라는 점을 착안, 그냥 택스트를 그대로 코드로 옮겨 적기로 했다.

#include <cassert>
#include <cstdio>
#include <math.h>
#include <iostream>


#define MIN(a,b) ((a)>(b)? (b):(a))


int N, K;
int a[500];


int main()
{
	scanf("%d %d", &N, &K);
	for (int i = 0; i < N; ++i) {
		scanf("%d", &a[i]);
	}


	double result = 987654321;
	for (int i = 0; i < N - K + 1; ++i) {
		for (int k = K; k < N - i + 1; ++k) {
			int sum = 0;
			for (int j = i; j < i + k; ++j) {
				sum += a[j];
			}
			double m = sum / (double)k;


			double dsum = 0;
			for (int j = i; j < i + k; ++j) {
				dsum += (a[j] - m)*(a[j] - m);
			}
			result = MIN(result, sqrt(dsum/(double)k));
		}
	}


	printf("%.11lf\n", result);
	return 0;
}

코드를 간단히 설명하자면, double result = 987654321; 이 부분 아래의 코드가 핵심 알고리즘인데,

i는 부분 순열의 시작 index를 / k는 부분 순열의 길이를 의미하고, j는 시작 index 부터 k개의 요소를 추척할 요량으로 변수를 할당했다.

단순 무식하게 텍스트 내용을 코드로 옮겨적은 거라 이해하기 쉬울듯? 

(1)첫번째 j 반복문에서 평균값 m을 구하기 위해 모든 요소를 전부 더하고

(2)두번째 j 반복문에서 분산을 구해준다. sqrt(dsum/k)가 분산!

cf) 평균값 m을 구할때 k를 double형으로 캐스팅 안해주면 (정수 / 정수) 로 소수점 이하가 버려진 평균값을 얻게 되므로 주의하자 -_- 왜캐 딱 나오나 의야했다.

(1) 같은 경우에는 부분합을 사전에 구해놓으면 평균값 m을 O(1) 시간에 찾을 수 있으나, N이 500이라는 점에서 굳이 그렇게 하지 않았다. 또 어차피 (2) 에서 O(N)의 반복을 해야하기 때문에 전체적인 시간 복잡도에 큰 영향은 없어보인다. 두번째 반복문도 상수시간에 할 수있는 방법이 고수님들은 알고 있겠지만 본인은 빠르게 푸느라 일단 저렇게...

## 수정

분산을 구할때 문제에서 제시한 수식이 아니라 

분산 = 제곱의 평균 - 평균의 제곱

인 점을 활용하면 부분합 배열을 만들어서 분산도 O(1) 시간에 찾을 수 있다.