[백준] 15954번 인형들 (= dolls) - 재우스 프로그래밍 (C 언어)

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

#include <stdio.h>
#include <math.h>

#define DEBUG 0
#define MAX_DOLL_COUNT 500

//input 값 저장
int arrInput[MAX_DOLL_COUNT];
//input에서 choiceBruteForce로 선택된 인형들 배열
int arrChoice[MAX_DOLL_COUNT];
//arrChoice 배열의 index
int arrChoiceIdx;
//N : 인형 개수, K : 최소 선택 인형 개수
int N, K;
//표준 편차의 최솟값
double result;

//input에서 표준편차를 계산할 인형 선택하는 함수
void choiceBruteForce(int);
//현재 arrChoice 에 들어있는 인형들의 표준편차를 계산하는 함수
void calcDeviation(void);

int main(void)
{
    //input 받기
    scanf("%d %d", &N, &K);
    for (int i = 0; i < N; i++) {
        scanf("%d", &arrInput[i]);
    }
    result = -1;

    //표준 편차를 계산할 인형들 선택하기
    for (int i = 0; i < N; i++) {
        choiceBruteForce(i);
    }

    printf("%.7lf\n", result);

    return 0;
}

void choiceBruteForce(int dollIdx)
{
    //arrChoice 배열 길이가 최소 선택 인형 개수보다 크거나 같을 때
    if (arrChoiceIdx >= K) {
        calcDeviation();
    }

    //dollIdx 위치의 인형 개수를 arrChoice에 추가
    arrChoice[arrChoiceIdx++] = arrInput[dollIdx];

    //연속된 위치에 있는 인형을 선택하므로 바로 다음 인형을 선택하거나 안하거나 둘 중 하나임.
    if (dollIdx < N) {
        choiceBruteForce(dollIdx + 1);
    }

    //backtracking을 위해 위에서 추가한 arrChoice 값 뺀다.
    arrChoice[--arrChoiceIdx] = 0;
    return;
}

void calcDeviation(void)
{
    int sum = 0;
    double avg = 0, varianceSum = 0, variance = 0, deviation = 0;

    //arrChoice의 합산 구함.
    for (int i = 0; i < arrChoiceIdx; i++) {
        sum += arrChoice[i];
    }
    //arrChoice의 평균 구함.
    avg = (double)sum / arrChoiceIdx;
    //분산 합 구함.
    for (int i = 0; i < arrChoiceIdx; i++) {
        varianceSum += pow(arrChoice[i] - avg, 2.0);
    }
    //분산 구함.
    variance = varianceSum / arrChoiceIdx;
    //표준 편차 구함.
    deviation = sqrt(variance);

#if DEBUG
    /*
    printf("arrChoice : ");
    for (int i = 0; i < arrChoiceIdx; i++) {
        printf("%d\t", arrChoice[i]);
    }
    */
    printf("\nsum: %d, avg: %lf, variance: %lf, deviation: %lf\tresult: %lf", sum, avg, variance, deviation, result);
#endif

    //표준 편차 최솟값 갱신
    if (result == -1) {
        result = deviation;
    }
    if (result > deviation) {
        result = deviation;
    }

    return;
}