ITES

#include 
#include 
#include 

using namespace std;

const unsigned int FIRST_SIGNAL = 1983;

int countK(unsigned int k, unsigned int n);

struct RNG {
	unsigned int seed;
	RNG() : seed(FIRST_SIGNAL) {}
	unsigned int next() {
		unsigned int ret = seed;
		seed = ((seed * 214013u + 2531011u));
		return ret % 10000 + 1;
	}
};

int main()
{
	int caseNum = 0;
	cin >> caseNum;

	unsigned int k = 0, n = 0;

	for (int cIter = 0; cIter < caseNum; cIter++)
	{
		cin >> k >> n;

		int count = countK(k, n);

		cout << count << endl;
	}
}

int countK(unsigned int k, unsigned int n)
{
	RNG rng;
	queue signals;
	unsigned int rangeSum = 0, cnt = 0;

	for (unsigned int tail = 0; tail < n; tail++)
	{
		int newSignal = rng.next();
		rangeSum += newSignal;
		signals.push(newSignal);

		while (rangeSum > k)
		{
			rangeSum -= signals.front();
			signals.pop();
		}

		if (rangeSum == k) { cnt++; }
	}

	return cnt;
}

 

ItesInput.txt

0.00MB

ItesOutput.txt

0.00MB

 

이 문제는 Input 값을 직접 생성해가며 문제를 풀어야 했다. Input 데이터들을 모아둘 메모리가 제한 범위를 훨씬 넘어서기 때문이다. 이 문제에서는 RNG 구조체를 선언하여 다음 Input 값을 매번 생성하였다.

 

알고리즘을 고안할 때 처음엔 brute force 방식으로 구현하였다. 모든 부분 순열 구간을 돌면서 값들을 계산하는 방식이었고, 매우 비효율적이었다. 책에서는 head 값이 증가할 때마다 tail 값이 감소하지 않는다는 지점에서 통찰을 얻었다. 이를 활용하여 tail 이 0 번부터 N - 1 번 순회하는 동안 head 들이 tail을 알아서 따라오도록 코드를 작성하였다.

그 결과 O(NK) 였던 brute force 방식을 O(N) 으로 훨씬 Optimize 할 수 있었다.

 

이 문제를 풀면서 RNG 구조체가 난수를 생성할 때 연산 관련 이슈가 발생했었다. 

자세한 건 아래 링크에 적어두었다.

참조> https://korsa.tistory.com/66