언제나 처음처럼

[문제 링크]

알고리즘 문제해결 전략 책에 있는 예제인데 투포인터를 응용한 재미있는 문제였다.

메모리 제한이 64MB 이하이므로 최대 50,000,000인 N을 배열에 담을 수 없다.

따라서 외계 신호를 받을때마다 구간합에 누적하고 결과값을 갱신해야 한다. 그리고 큐에 누적시킨 외계 신호를 보관하고 있다가 구간합이 K보다 커지게 되면 구간합이 K보다 같거나 작아질 때까지 먼저 들어온 순서대로 빼준다.

구간합이 K와 같다면 신호와 일치한 것이므로 결과값을 1 증가시킨다.

#include <iostream>
#include <queue>
#include <cmath>
using namespace std;

const long long MOD = pow(2, 32);

class Signal
{
	long long num;

public:
	Signal() : num(1983) {}
	int next()
	{
		long long ret = num;
		
		num = (num * 214013 + 2531011) % MOD;
		
		return ret % 10000 + 1;
	}
};

int main(void)
{
	int tc;
	cin >> tc;

	while (tc--)
	{
		int K, N;
		cin >> K >> N;

		Signal signal;
		queue<int> range;
		int ret = 0, rangeSum = 0;

		for (int i = 0; i < N; i++)
		{
			int nextSignal = signal.next();
			rangeSum += nextSignal;
			range.push(nextSignal);

			while (rangeSum > K)
			{
				rangeSum -= range.front();
				range.pop();
			}

			if (rangeSum == K)
				ret++;
		}

		cout << ret << endl;
	}
	return 0;
}

알고리즘 200일 프로젝트 - 136 day