algospot - FESTIVAL

문제

커다란 공연장을 빌려서 록 페스티벌을 개최하려고 합니다. 이 페스티벌은 여러 날 동안 진행되며, 하루에 한 팀의 밴드가 공연장에서 콘서트를 하게 됩니다. 전체 밴드를 몇 팀 섭외할 지는 아직 결정하지 않았지만, 페스티벌의 간판 스타인 L개의 팀은 이미 섭외가 끝난 상태입니다. 따라서 페스티벌은 최소 L일 이상 진행하게 됩니다.

이번에 사용할 공연장은 하루 빌리는 데 드는 비용이 매일 매일 다릅니다. 때문에 공연 일정을 잘 정해서 공연장 대여 비용을 줄이려고 합니다. 앞으로 N일간의 공연장 대여 비용을 알고 있다고 합시다. 이 중 L일 이상을 연속해서 대여하되, 공연장을 하루 빌리는 데 드는 평균 비용을 최소화하려면 어떻게 공연장을 빌려야 할까요?

예를 들어 앞으로 6일간 공연장을 빌리는 데 드는 비용이 각 {3, 1, 2, 3, 1, 2}라고 합시다. 이미 세 팀을 섭외했다고 하면, 3일 대신 4일 동안 공연을 진행해서 평균 비용을 더 저렴하게 할 수 있습니다. 3일 동안의 평균 대여 비용을 최소화하는 방법은 2일째부터 4일째까지 공연장을 대여하는 것인데, 이 때 하루 평균 (1+2+3)/3 = 2의 비용이 듭니다. 반면 2일째부터 5일째까지 공연장을 대여하면 평균 비용이 (1+2+3+1)/4 = 7/4밖에 되지 않습니다.

입력

입력의 첫 줄에는 테스트 케이스의 수 C (C ≤ 100)가 주어집니다. 각 테스트 케이스의 첫 줄에는 공연장을 대여할 수 있는 날들의 수 N (1 ≤ N ≤ 1000)과 이미 섭외한 공연 팀의 수 L (1 ≤ L ≤ 1000, L ≤ N)이 주어집니다. 그 다음 줄에는 N개의 숫자로 공연장 대여 비용이 날짜별로 주어집니다. 모든 비용은 100 이하의 자연수입니다.

출력

입력에 주어지는 각 테스트 케이스마다 한 줄에 최소의 평균 대여 비용을 출력합니다. 10-7 이하의 절대/상대 오차가 있는 답은 정답 처리됩니다.

 

예제 입력

2

6 3

1 2 3 1 2 3

6 2

1 2 3 1 2 3

 

예제 출력

1.75000000000

1.50000000000

코드

#include <stdio.h>

int cost[1000];

int main(){
	char temp;
	int C, N, L;
	int i, j, k;
	int size, offset, iter, sum;
	double avg, min;

	scanf("%d", &C);

	for(i = 0; i < C; i++){
		min = 100000;
		scanf("%d %d", &N, &L);
		j = 0;

		do {
			scanf("%d%c", &cost[j], &temp);
			j++;
		} while(temp != '\n');

		for(k = L; k <= N; k++){
			size = k;
			offset = 0;

			do {
				iter = 0;
				sum = 0;

				do {
					sum += cost[offset+iter];
					iter++;
				} while(iter < size);

				avg = (double)sum / size;

				if(avg < min)
					min = avg;
				
				offset++;
			} while(offset + size <= N);

		}

		printf("%.11lf\n", min);
	}

	return 0;
}

해설

공연장을 연속으로 빌리는 최소 일 수 L부터 N까지의 공연 평균 비용을 전부 계산 했다. 예를 들어 N = 6, L = 3이고, 비용은 (1, 2, 3, 1, 2, 3)일 때, 공연을 빌리는 일 수를 size라고 하면, 다음과 같은 경우의 수가 발생한다.

 

i) size = 3(L부터)

(1, 2, 3), (2, 3, 1), (3, 1, 2), (1, 2, 3)

ii) size = 4

(1, 2, 3, 1), (2, 3, 1, 2), (3, 1, 2, 3)

iii) size = 5

(1, 2, 3, 1, 2), (2, 3, 1, 2, 3)

iv) size = 6(N까지)

(1, 2, 3, 1, 2, 3)

 

각 경우의 수의 평균 비용을 모두 계산하고, 최소 평균 비용을 구한다.

낙서

출력할 때 소수점 자릿수를 맞춰주지 않으면 답으로 인정되지 않는 것 같다.

 

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