[알고스팟/C,C++] FESTIVAL: 록 페스티벌

www.algospot.com/judge/problem/read/FESTIVAL

algospot.com :: FESTIVAL

시간제한이 널널해 완전 탐색, 즉 브루트포스 알고리즘으로도 해결이 가능한 문제입니다.

#include<iostream>

using namespace std;

double getCost(int* cost, int n, int l)
{
    double avg, res = 1000000;

    for (int i = l; i <= n; i++) {
        for (int j = 0; j <= n - i; j++) {
            avg = 0;
            for (int k = j; k < j + i; k++) {
                avg += cost[k];
            }
            avg /= i;
            if (avg < res) {
                res = avg;
            }
        }
    }

    return res;
}

int main(void)
{
    int c; cin >> c;
    cout.precision(10);
    cout << fixed;

    for (int i = 0; i < c; i++) {
        int n, l; cin >> n >> l;
        int* cost = new int[n];
        for (int j = 0; j < n; j++) {
            cin >> cost[j];
        }
        cout << getCost(cost, n, l) << endl;
    }

    return 0;
}

getCost 함수의 i는 며칠(3~6일)을 탐색해볼지를 의미하고, j는 탐색 시작 지점을 의미합니다. 3일의 경우 3, 4, 5가 마지막 탐색 구간이기 때문에 탐색 시작 지점은 0, 1, 2, 3이 될 수 있겠네요. k는 실제 탐색 지점들을 의미합니다. 모든 탐색을 끝마친 뒤 가장 작은 평균 비용을 반환합니다.