본문 바로가기
알고리즘, 자료구조/알고리즘

[Queue] 19.5 외계 신호 분석

by Wordbe 2019. 8. 27.
728x90

이 문제는 종만북, '알고리즘 문제해결 전략 2' 에 나와있는 예제 입니다.

 

RNG를 만드는 방법,

입력이 너무커서 한번에 넣지 못하니, 온라인 알고리즘을 만드는 법을 배웠습니다.

 

또한 구간합을 탐색하는 데 이미 계산한 것들을 queue에 push하여 담고,

필요없는 것들을 즉각적으로 pop하여 필요한 구간합만 계산하는 아이디어도 얻었습니다.

 

#define _CRT_SECURE_NO_WARNINGS
#include <cstdio>
#include <queue>

using namespace std;

// 선형 합동 난수 생성기(Linear congruential random number generator)
struct RNG {
	unsigned seed;
	RNG() : seed(1983) {}
	unsigned next() {
		unsigned ret = seed;
		seed = ((seed * 214013u) + 2531011u);
		return ret % 10000 + 1;
	}
};

int countRange(int k, int n) {
	RNG rng;
	queue<int> range;
	int ans = 0, range_sum = 0;

	// O(N)
	for (int i = 0; i < n; ++i) {
		int new_signal = rng.next();
		range_sum += new_signal;
		range.push(new_signal);

		// 구간합이 k보다 크면, 구간에서 그 신호를 뺀다.
		while (range_sum > k) {
			range_sum -= range.front();
			range.pop();
		}

		if (range_sum == k) ans++;
	}

	return ans;
}

int main() {
	RNG rng;
	for (int i = 0; i < 10; ++i) {
		printf("%d ", rng.next());
	}

	int T, K, N;
	scanf("%d", &T);
	while (T--) {
		scanf("%d %d", &K, &N);
		printf("%d\n", countRange(K, N));
	}
	
	return 0;
}
728x90

'알고리즘, 자료구조 > 알고리즘' 카테고리의 다른 글

[Deque] 5430 AC (백준)  (0) 2019.08.28
[Deque] 1021 회전하는 큐  (0) 2019.08.27
[Disjoint Set] 1717 집합의 표현  (0) 2019.08.26
[1931] 회의실배정  (0) 2019.07.29
2217 로프  (0) 2019.07.25

댓글