[APSS] Rock Festival

1. Algospot - FESTIVAL

"알고리즘 문제해결 전략" 초반부에 나오는 문제다. 혹은
알고스팟 (algospot) : https://algospot.com/judge/problem/read/FESTIVAL 
에서 확인할 수 있다.

연속된 날짜 중에 최소 L개를 선택한 날짜의 평균이 가장 작은 경우를 구하는 문제다.
문제의 범위 자체가 크지 않기 때문에 (많아봐야 10^9을 넘을 수가없음.) 단순히 시간복잡도 O(n^2)으로 풀어도 충분했다.



풀이

1. 첫번째 for문에서 날짜의 비용을 담은 Buffer 배열의 처음부터 N-L까지 탐색한다. 이 때 최소 L개를 선택해야하기 때문에 L만큼 빼준다. 이 때 비용의 합을 담는 변수인 sum과 날짜의 개수를 담는 변수인 count는 처음으로 돌아가 탐색하게 될 경우 0으로 초기화해준다.

for(int i = 0; i <= N - L; i++){

            sum = 0;
            count = 0;

            ...

}

2. i부터 L+i까지의 날짜 당 비용을 전부 합해준다. 시작 날짜(i)는 Buffer의 인덱스의 처음부터 탐색하므로 시간에 따라 변하기 때문에 i부터 L개를 선택한 날짜까지의 합을 구해줘야한다. 그 후 최소비용을 비교 후 업데이트 해준다.

for(int j = i; j < L + i; j++){
                sum += Buffer[j];
                count++;
            }

result = lessValue(sum / count, result);

3. 마지막으로 L까지의 합의 평균부터 N까지의 합의 평균을 계속 비교하여 최소비용을 구하고 최소비용을 출력해주면 되겠다.

for(int k = L + i; k < N; k++){

                sum = sum + Buffer[k];
                count++;
                result = lessValue(sum / count, result);

}

출처 : 알고리즘 문제해결 전략 (Algorithmic Problem Solving Strategies)
소스코드 : https://github.com/betterafter/AlgoStudy/blob/master/APSSCoding/RockFestival.c