algospot FESTIVAL 록 페스티벌

문제

https://algospot.com/judge/problem/read/FESTIVAL

걸린 시간

01 : 21 : 04

풀이

C++

#include <stdio.h>
#include <iostream>
#include <float.h>
#include <vector>
#include <string.h>
using namespace std;

int N, L;
int cost[1000];

int main(){
    int C;
    scanf("%d", &C);
    while(C--){
        scanf("%d %d", &N, &L);
        memset(cost, 0, sizeof(cost));
        for(int i = 0; i < N; i++)
            scanf("%d", &cost[i]);
        double aver = DBL_MAX;
        for(int i = L; i < N+1; i++){
            double sum = 0;
            int s = 0; // start
            int e = 0; // end
            for(int j = 0; j < N; j++){
                if(j > i-1)
                    sum -= cost[s++];
                sum += cost[e++];
                if(j > i-2 && sum/i < aver)
                    aver = sum/i;
            }
        }
        printf("%.8lf\n", aver);
    }
    return 0;
}

종만북 맨 처음에 나오는 난이도 하 문제로 시간 초과가 나지 않게 슬라이딩 윈도우 기법을 사용해 제출하였는데 오답 처리가 됐다.

몇번을 다시 봐도 알고리즘에는 문제가 없는 것 같아 댓글을 참고했더니 여러 사람이 공통적으로 앓고 있었던 자료형 문제였다.

float 자료형을 사용할 경우 소수점 이하 6자리만을 표현할 수 있으므로 10^-7 이하의 절대/상대 오차값만을 허용해주는 문제의 조건을 생각했을 때, 소수점 이하 15자리 까지 표현이 가능한 double 자료형을 사용해야 문제가 없다고 한다.

또 출력값의 범위를 최소한 소수점 이하 8번째 자리까지 출력해야 정답 처리를 받을 수 있다. 소수점 이하 7번째 자리까지 출력한다면 8번째 자리에서 반올림한 값이 정답에 영향을 미칠 수 있기 때문이다.