록 페스티벌(FESTIVAL)

시간 제한이 2초로 넉넉하므로 모든 경우의 수를 계산하도록 했다.

3 1 2 3 1 2 의 비용이 들고 L=3일 때, 

(3 + 1 + 2) / 3

(3 + 1 + 2 + 3) / 4

(3 + 1 + 2 + 3 + 1) / 5

(3 + 1 + 2 + 3 + 1 + 2) / 6

(1 + 2 + 3) / 3

...

(3 + 1 + 2) / 3

까지 모든 경우의 수에서 평균 비용이 최소가 되는 값을 출력하도록했다.

시간복잡도는 O(n^2)

#include <stdio.h>
 
int main(void)
{
    int c;
    scanf("%d", &c);
    for (int T = 0; T < c; T++)
    {
        int n, l;
        scanf("%d%d", &n,&l);
        int day[1001]; //비용을 저장할 배열
        for (int i = 0; i < n; i++) 
        {
            scanf("%d", &day[i]);            
        }
        double min = 2e9;//평균의 최솟값
        for (int i = 0; i < n; i++)
        {
            int sum = 0;
            int cnt = 0;
            for (int j = i; j < n; j++)
            {
                sum += day[j];
                cnt++;
                if (cnt < l)
                {
                    continue;
                }
                else
                {
                    if ((double)sum / cnt < min)
                    {
                        min = (double)sum / cnt;
                    }
                }
            }
        }
        printf("%.10lf\n", min);
    }
    return 0;
}