19.6 외계 신호 분석

외계로부터 신호의 부분 수열 중 합이 K인 것이 몇 개인지 찾는 문제입니다.

 

외계로부터의 신호는 다음과 같이 생성됩니다.

A[0]=1983

A[i] = (A[i-1] * 214013 + 2531011) mod 2^32

i번째 입력 신호는 A[i-1] mod 10000 +1 입니다.

(ex. 1984, 8791, 4770, 7665, 3188, ....)

 

N: 신호 배열의 길이, K: 합

 

K<=5,000,000, N<=50,000,000

 

신호의 모든 값을 계산해 그 때부터 합이 K인 것을 찾기에는 메모리가 너무 많이 듭니다. (제한 64MB) 그러므로 '온라인 알고리즘' 을 이용하여 입력 전체에 대해 메모리를 사용하지 않도록 합니다.

 

온라인 알고리즘이란, 전체 입력이 한번에 주어지지 않아도 계산을 할 수 있는 알고리즘입니다. 대표적인 예로 삽입 정렬이 있습니다.

 

온라인 알고리즘을 사용하기 전에 N개의 원소들에 대해 계산하고자하는 처음 위치를 head, 끝 위치를 tail 이라고 합시다. head부터 tail까지 합을 구하고, tail 다음 원소가 tail이 되었을 때 그 합이 K보다 크다면 그 이후는 계산하지 않아도 됩니다. 

그리고 head를 한 칸씩 다음 원소에 대해 적용할 때, 후보다 되는 tail을 기존 tail에서부터 시작하여도 됩니다. 왜냐하면, head부터 tail까지 합이 K였는데 그 사이의 원소들은 아무리 더해도 K보다 작습니다. 그러므로 새로운 head부터 탐색이 아닌, 기존의 tail에서부터 계산하여도 됩니다.

 

코드

#include<iostream>
#include<vector>
#include<algorithm>
#include<queue>

using namespace std;

int C, K, N;

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

int countRanges(int k, int n) {
	RNG rng;
	queue<int>range;
	int ret = 0, rangeSum = 0;

	for (int i = 0; i < n; i++) {
		int newSignal = rng.next();
		rangeSum += newSignal;
		range.push(newSignal);

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

		if (rangeSum == k)
			ret++;
	}
	return ret;
}

int main()
{
	cin >> C;
	while (C--) {
		cin >> K >> N;
		cout << countRanges(K, N) << '\n';
	}
}

결과