[백준 15954번] 인형들 (C++)

2018 카카오 코드 페스티벌 예선 2번 문제

 

www.acmicpc.net/problem/15954

15954번: 인형들

 

 

처음에 문제가 이해되지 않아 겁먹고 포기할 뻔 했는데

반복해서 읽어보니 걱정만큼 어려운 문제가 아니어서 찬찬히 풀 수 있었다!

 

 

 

 

마찬가지로 곧장 코드를 짜기 전에 어떻게 풀 것인지 손코딩으로 생각해봤다.

 

 

우선 N 개의 인형의 나열 순서는 input으로 받기 때문에 고정되어 있었다.

내가 할 일은 이 고정된 인형의 순서에서 K개 이상의 연속된 인형들의 최소 표준편차를 구하는 일이었다.

 

 

가령, 테스트케이스 2처럼

N=10, K=3이라면

3개의 연속된 인형, 4개의 연속된 인형, 5개의 연속된 인형, ... , 10개의 연속된 인형 각각의 경우의

표준편차 중 최소값을 골라내면 되는 것이다.

 

여기서 중요한 건 3개의 연속된 인형도 1번~3번 인형, 2번~4번 인형, 3번~5번 인형, ... 8번~10번 인형

이렇게 8개의 조합이 나올 수 있다는 거다. (4개, 5개 ,... 10개의 연속된 인형의 경우도 그 조합의 가짓수가 다양하기는 마찬가지다.)

 

 

 

그럼 어떻게 푸는 게 좋을까??

 

예를 들어 5개의 연속된 인형의 표준편차를 구하는 일에는 다음과 같이

가장 처음 HEAD=0, TAIL=4로 초기화해서 HEAD와 TAIL사이의 인형의 선호하는 사람 수에 대한 표준편차를 구하고

그 다음 HEAD와 TAIL을 1씩 증가시켜 배열의 마지막 인덱스에 도달할 때 까지 표준편차 구하는 것을 반복하면 된다.

 

최소값은 반복문 내에서 바로 바로 갱신해주면 된다. 

 

즉, HEAD와 TAIL이라는 iterator를 반영하여 구해주면 된다.

[예시] 10개의 인형 중 5개의 연속된 인형들의 표준편차를 구하는 방식

 

 

 

이러한 방식으로 알고리즘을 설계한 다음 코드를 짜기 시작했다.

 

 

main문에서는 최소한의 작동만 해야하므로

위 알고리즘을 수행할 2개의 함수를 구현했는데

 

(1) head와 tail을 배열 내에서 이동시키면서 최소 표준편차를 찾아내는 함수

(2) 위 (1)함수가 전달해주는 head와 tail을 바탕으로 표준편차를 계산해서 전달해주는 함수

 

이렇게 두 가지 이다.

 

 

하나씩 살펴보도록 하자.

 

 

 

 

 

 

우선 전역변수는 다음과 같다.

 

int N;
int K;

int doll_arr[501];

doll_arr는 인형 순서를 입력받을 배열이다.

 

 

 

 

 

 

다음 표준편차를 구하는 함수이다.

double Calculator_SD(int _head, int _tail) //Smallest_SD()에서 계산하고자 하는 수열의 표준편차를 계산한 뒤 리턴해준다.
{
	double mean = 0;
	double sd = 0;
	int num = _tail - _head + 1;

	for (int j = _head; j <= _tail; j++)
	{
		mean += doll_arr[j];
	}
	mean /= num; //평균값 구하기

	for (int j = _head; j <= _tail; j++)
	{
		double temp = (doll_arr[j] - mean);
		temp *= temp; //제곱
		sd += temp; //제곱값 합산
	}
	sd /= num;
	sd = sqrt(sd);

	return sd;
}

num은 몇 개의 연속된 인형인지를 저장하는 변수이다.

배열의 head부터 tail까지에 해당하는 각 인형의 선호하는 사람 수를 모두 더한 후 num으로 나누어주어 평균을 구하고

다시 head부터 tail까지 해당하는 각 인형의 선호하는 사람 수와 평균의 차의 제곱을 합산한 뒤 num으로 나누어 

분산을 구했다.

 

 

마지막으로 분산에 루트를 씌워 표준편차를 구한 뒤 리턴한다.

 

 

 

 

 

 

 

 

 

 

다음은 핵심이 되는 함수이다.

double Smallest_SD() //최소가 되는 표준 편차를 리턴한다.
{
	int head = 0; //배열의 head
	int tail = 0; //배열의 tail
	double smallest = 100000000;

	for (int i = K-1; i < N; i++) //가령 N=10, K=3일 경우, 반복문은 2,3,4,..,9 총 8회를 돈다.
	{
		head = 0;
		tail = i;

		while (tail < N)//즉 tail이 배열의 마지막 인덱스에 닿기 전까지 반복
		{
			double temp = Calculator_SD(head, tail);

			if (smallest >= temp)
			{
				smallest = temp;
			}//최솟값 갱신

			head++;
			tail++; 
		}
	}

	return smallest;
}

k개 이상의 가능한 모든 인형의 나열에 대한 표준편차를 계산하여 최솟값에 해당하는 표준편차를 smallest에 저장한다.

이 후 head와 tail을 1씩 옮겨가며 반복문을 수행한다.

 

 

 

 

 

 

 

 

 

그럼 이제 전체 코드를 살펴보자.

 

#include <iostream>
#include <cmath>
using namespace std;

int N;
int K;

int doll_arr[501];


double Calculator_SD(int _head, int _tail) //Smallest_SD()에서 계산하고자 하는 수열의 표준편차를 계산한 뒤 리턴해준다.
{
	double mean = 0;
	double sd = 0;
	int num = _tail - _head + 1;

	for (int j = _head; j <= _tail; j++)
	{
		mean += doll_arr[j];
	}
	mean /= num; //평균값 구하기

	for (int j = _head; j <= _tail; j++)
	{
		double temp = (doll_arr[j] - mean);
		temp *= temp; //제곱
		sd += temp; //제곱값 합산
	}
	sd /= num;
	sd = sqrt(sd);

	return sd;
}



double Smallest_SD() //최소가 되는 표준 편차를 리턴한다.
{
	int head = 0; //배열의 head
	int tail = 0; //배열의 tail
	double smallest = 100000000;

	for (int i = K-1; i < N; i++) //가령 N=10, K=3일 경우, 반복문은 2,3,4,..,9 총 8회를 돈다.
	{
		head = 0;
		tail = i;

		while (tail < N)//즉 tail이 배열의 마지막 인덱스에 닿기 전까지 반복
		{
			double temp = Calculator_SD(head, tail);

			if (smallest >= temp)
			{
				smallest = temp;
			}//최솟값 갱신

			head++;
			tail++; 
		}
	}

	return smallest;
}



int main()
{
	cin >> N >> K;
	for (int i = 0; i < N; i++)
	{
		cin >> doll_arr[i];
	} // 테스트케이스를 입력받아 배열에 저장한다.

	cout.precision(10);
	cout << Smallest_SD() << "\n"; //정답이 되는 최소 표준편차를 출력한다.

	return 0;

}

여기서 중요한 건 표준편차의 오차가 소숫점 6자리 이하여야 한다고 했으므로

안전하게 precision(10)으로 설정하여 총 10자리를 출력하도록 하자. 

 

6자리 딱 맞춰서 출력하면 틀린다ㅎㅎ..

 

 

 

 

 

 

아무튼 제출 결과  무사히 정답!