최대 1 분 소요

풀이 코드

#include <iostream>
using namespace std;

#define MAX_DAY 1000
int dp[MAX_DAY];
double min_cost = 100000;
double mean_cost;

int main(void)
{
    ios_base :: sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    int C, N, L;
    cin >> C;

    for (int c = 0; c < C; c++) {
        cin >> N >> L;
        for (int n = 0; n < N; n++) cin >> dp[n];

        for (int i = 0; i < N; i++) {
            double sum = 0;
            for (int j = 0; j < N - i; j++) {
                sum += dp[i + j];
                if (j >= L - 1) {
                    mean_cost = sum / (j + 1);
                    min_cost = mean_cost < min_cost ? mean_cost : min_cost;
                }
            }
        }
        printf("%.9lf\n", min_cost);
        min_cost = 100000;
    }
    return 0;
}

접근

처음엔 모든 부분합을 저장하는 2차원 배열을 만들어 DP로 풀려고 했는데, 굳이 그럴 필요가 없었다.

최소 금액만 알면 되는 거잖아? 그럼 반복문 내에서 L개의 합이 발생할 때마다 최소 값을 갱신하면 되는 거.

기록

처음엔 float를 썼지만 오답…

다음엔 double을 썼지만 또 오답…

long double로 바꿔써도 오답…

결국 printf()에서 %.9lf로 출력 형식을 지정하니 맞더라~

참고