[종만북 문제] 록 페스티벌 (난이도: 하, 문제 ID : FESTIVAL)

프로그래밍 대회에서 배우는 알고리즘 문제해결 전략(이하 종만북)에서 소개된 문제를 풀이합니다. 알고리즘에 진심이시라면, 직접 구매하셔서 읽어보시는 것을 추천합니다!

---

핵심 :

1. 기본적으로는 이중 for-loop 으로 풀 수 있으나, DP 를 사용하면 시간을  조금 단축할 수 있다.

2. 소수점 오차에 유의하자.

---

록 페스티벌 (난이도: 하, 문제 ID : FESTIVAL)

사실 2중 for-loop 만 돌리면 쉽게 풀 수 있는 문제이긴 하다. 따라서 따로 설명을 길게 적지는 않고, 코드에 주석을 조금 달아 두었다! 😄

#include <iostream>
#include "stdlib.h"

using namespace std;

int N, L;
int days[1000];
int dp[1000];
double ans;

double minVal(double a, double b)
{
	if (a < b) return a;
	else return b;
}

void sol()
{
	ans = 987654321.0;

	// L 크기 만큼의 Sum 을 미리 계산
	int tempSum = 0;
	for (int i = 0; i < L; ++i)
		tempSum += days[i];
	dp[0] = tempSum;
	for (int i = 1; i - 1 + L < N; ++i)
	{
		tempSum -= days[i - 1];
		tempSum += days[i - 1 + L];
		dp[i] = tempSum;
	}

	// L 크기인 녀석을 먼저 비교
	for (int i = 0; i < N - L + 1; ++i)
		ans = minVal(ans, (double)dp[i] / L);

	// L+1 ~ N 사이의 크기의 평균값 비교
	for (int l = L + 1; l <= N; ++l)
	{
		for (int i = 0; i + l - 1 < N; ++i)
			dp[i] += days[i + l - 1];

		for (int i = 0; i < N - l + 1; ++i)
			ans = minVal(ans, (double)dp[i] / l);
	}
}

int main()
{
	int cases;
	cin >> cases;
	while (cases--)
	{
		cin >> N;
		cin >> L;

		for (int i = 0; i < N; ++i)
			cin >> days[i];

		sol();

		// ans 는 double 이어야 하며, cout 을 쓰면 오답처리임에 유의(실수 오차)
		printf("%.12f\n", ans);
		//cout << ans << endl;
	}

	return 0;
}