algospot FESTIVAL

문제 : https://www.algospot.com/judge/problem/read/FESTIVAL

 

문제난이도 : 알고리즘 문제해결전략(하)

 

이해를 간단히 돕자면

N 일간의 콘서트장 대여비를 미리 알고있는 상황에서 최소 L 개의 팀이 주어졌을때 (팀의 수는 이미정해진팀+@ )

몇일을 대여하는 것이 평균적으로 가장 싼 비용이 되는가 하는 문제이다.

* 단, 연속해서 대여해야 한다.

 

문제를 접근해보자면

눈에 띄는 것이 연속해서 대여한다는 점이였다.

결국 구간합에대한 구간크기의 길이로 나눈 값이 제일 작은 비용을 찾으면된다.

 

N의 범위는 1-1000이고 시간제한은 2초, 테스트케이스는 최대 100개

그냥 무난하게 2중포문으로 반복문만 돌려도 100N^2 이여서 무난히 시간을 통과할 것 같았다.

 

나는 간단히

1 2 3 1 2 3 이라는 대여값을 받으면

1 3 6 7 9 12 이렇게 값을 연속으로 더해놓고,

L의 최소값부터 L 이 N 이 될때까지 반복문을 통해서 구현하였다.

 

#include <cstdio>
#pragma warning(disable:4996)
int arr[1001];
int dp[1001];
int main() {
    int T, N, L;
 
    scanf("%d", &T);
    while (T--) {
        scanf("%d%d", &N, &L);
 
        for (int i = 1; i <= N; i++)
            scanf("%d", &arr[i]);
 
        for (int i = 1; i <= N; i++) {
            dp[i] = dp[i - 1] + arr[i];
        }
 
        double min = (double)dp[L]/L;
        double check;
        for (int i = L; i <= N; i++) {
            for (int k = i; k <= N; k++) {
                check = (double)(dp[k] - dp[k - i]) / i;
                if (check < min) min = check;
            }
        }
        printf("%.10f\n", min);
    }
    return 0;
}