[ALGOSPOT] 록 페스티벌

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

algospot.com :: 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

 

---

풀이1

• C (C ≤ 100) : test case 수
• N (1 ≤ N ≤ 1000)
• L (1 ≤ L ≤ 1000, L ≤ N)

N개의 data가 있다. L 이상 N 이하의 window로 N개의 data를 탐색한다.

각 window의 mean값을 계산하여, minMean을 구하려고 한다.

 

N개의 data를 L개의 window로 전체 탐색하기 때문에, 연산횟수는 N * L로 계산된다.

10^6이다. test case가 100개이므로, 10^8이다. 그러므로 제한시간 2초 이내에는 충분하다.

 

어떻게 구현하면 좋을까?

N개의 data를 전체탐색하면서, window값의 mean값을 계산하고자 한다.

mean값을 계산하는 책임은 meanTracker에게 줬다.

 

시퀀스는 다음과 같다.

- N개의 data를 전체탐색한다.

- meanTracker가 data를 더한다.

- meanTracker가 ready가 되면, mean값을 요청한다.

- minMean을 업데이트한다.

 

그런데 구현을 하다보니 문제가 있다.

N개의 Data를 (N - L + 1)번 전체탐색을 해야한다.

처음에는 전체탐색을 할 때, N개의 Data를 입력받으려고 했다. 그러나 2회 째의 입력을 따로 받을 수 없다.

그래서, N개의 Data를 따로 배열로 저장해두려고 한다. 그러면 연산 횟수가 tc마다 N번 이상 증가한다.

즉, (10^6 + 10^3) * 10^2이다. 그래도 10^9보다는 작기 때문에, 제한 시간 2초는 충분하다.

 

처음에 오답이었다. window가 다 채워진 상태에서 다음 데이터를 추가할 때, 이전 데이터를 제거하고 추가해야한다.

이 로직에 오류가 있어서, 디버깅하는데 시간이 좀 걸렸다. TC와 디버깅 로그를 추가해서 해결할 수 있었다.

 

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif

#include <stdio.h>
#include <string.h>

#define MAX_MEAN (100 * 1000)
#define MAX_SIZE (1000 + 1)

class MeanTracker
{
public:
	void init(int n)
	{
		memset(data, 0, sizeof(data));
		count = 0;
		pi = 0;
		ci = 0;
		windowSum = 0;
		windowCnt = n;
	};
	void addVal(int v)
	{
		if (count >= windowCnt)
		{
			windowSum -= data[ci];
			ci = (ci + 1) % windowCnt;
		}

		data[pi] = v;
		count++;
		
		windowSum += data[pi];
		pi = (pi + 1) % windowCnt;
	};

	void printDebug(void)
	{
		printf("pi=%d, ci=%d, count=%d, windowSum=%d, windowCnt=%d, avg=%.11f, data=",
			pi, ci, count, windowSum, windowCnt, calculate());
		
		int index = ci;
		for (int i = 0; i < windowCnt; i++)
		{
			printf("%d ", data[index]);
			index = (index + 1) % windowCnt;
		}
		printf("\n");
	};

	bool isReady(void) const
	{
		return (count >= windowCnt);
	};
	double calculate()
	{
		return (static_cast<double>(windowSum) / windowCnt);
	};

private:
	int data[MAX_SIZE];
	int count;
	int pi;
	int ci;
	int windowCnt;
	int windowSum;
};

int main() {
	setbuf(stdout, NULL);
	freopen("input.txt", "r", stdin);

	int T;
	MeanTracker meanTracker;

	scanf("%d", &T);
	int rawData[MAX_SIZE];

	for (int tc = 1; tc <= T; tc++)
	{
		int N, L;
		scanf("%d %d", &N, &L);
		//printf("%d %d\n", N, L);
		
		for (int i = 0; i < N; i++)
		{
			scanf("%d", &rawData[i]);
		}

		double minMean = MAX_MEAN;
		for (int l = L; l <= N; l++)
		{
			meanTracker.init(l);

			// window: n
			for (int i = 0; i < N; i++)
			{
				meanTracker.addVal(rawData[i]);

				if (meanTracker.isReady())
				{
					double mean = meanTracker.calculate();
					meanTracker.printDebug();
					if (mean < minMean) minMean = mean;
				}
			}
		}
		printf("%.11f\n", minMean);
	}

	return 0;
}

 

 

풀이2

풀이1의 경우, 120ms가 나왔다. 시간을 더 줄일 수 없을까?

다른 풀이를 보면, n ms 이내의 풀이도 있다.

 

1. 입력 데이터를 따로 배열(rawData[MAX_SIZE])로 잡아서 들고 있어야 할까?

2. window가 data를 들고 있어야 할까? mean값이 필요한 건데, sum으로 들고 있어도 되지 않을까?

 

다른 풀이를 보니 부분합 개념을 사용했다. 부분합이란?

 

부분합을 사용하면, window마다 N개의 데이터를 항상 전체탐색을 하지 않는다.

풀이 1은 L이상 N이하의 window들에 대해서 항상 N개의 데이터를 전체탐색했다.

그러나, N - L + 1 개의 데이터만 전체탐색을 하면 되기 때문에, L이 N의 가까워질 수록

(1 + 2 + 3 .. + N)번 탐색이니까 결국 탐색 수가 약 절반으로 줄어든다.

 

풀이 1보다 시간이 절반 이상 줄었다.

#ifndef _CRT_SECURE_NO_WARNINGS
#define _CRT_SECURE_NO_WARNINGS
#endif

#include <stdio.h>
#include <string.h>

#define MAX_MEAN (100 * 1000)
#define MAX_SIZE (1000 + 1)

int main() {
	setbuf(stdout, NULL);
	freopen("input.txt", "r", stdin);

	int T;

	scanf("%d", &T);

	for (int tc = 1; tc <= T; tc++)
	{
		int N, L;
		scanf("%d %d", &N, &L);
		//printf("%d %d\n", N, L);
		
		int rawData[MAX_SIZE];
		int prefixSum[MAX_SIZE];
		double minMean = MAX_MEAN;

		// 입력
		for (int i = 0; i < N; i++)
		{
			scanf("%d", &rawData[i]);
			if (0 == i)
			{
				prefixSum[i] = rawData[i];
			}
			else
			{
				prefixSum[i] = prefixSum[i - 1] + rawData[i];
			}
		}
		
		for (int length = L; length <= N; length++)
		{
			for (int i = 0; i <= N - length; i++)
			{
				int sum = prefixSum[i + length - 1];
				if (i > 0) sum -= prefixSum[i - 1]; // 구간 합 계산

				double mean = (double)sum / length;
				if (mean < minMean) minMean = mean;
			}
		}

		printf("%.11f\n", minMean);
	}

	return 0;
}

 

정리

구간 합을 구할 때, 구간이 동적으로 변하는 경우는 sliding window가 적합하고, 그렇지 않은 경우는 prefix sum이 적합하다.