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 |
댓글