algospot 외계 신호 분석 (문제 ID: ITES) c++

알고스팟 문제 링크: https://algospot.com/judge/problem/read/ITES

algospot.com :: ITES

숫자들이 순차적으로 주어졌을때 해당 수열의 부분수열 합이 k인 경우의 수를 찾는 문제이다.

 

수열의 길이가 최대 50000000인것을 감안하면 수열을 값을 미리 계산하여 배열을 선언하고 거기에 담는 방식은 불가능 하다.

다른 방법으로는 프로그램이 실행될때 실시간으로 값을 생성하는것이 있다.

이를 위해서 구조체와 메서드를 작성하고 순차적으로 값을 생성해서 큐에 넣어 관리한다.

 

	#include<iostream>
	#include<queue>
	using namespace std;
	int k, n;
	// 실시간으로 입력을 생성하기 위한 구조체
	struct RNG {
	unsigned seed;
	RNG() : seed(1983) {}
	unsigned next() {
	unsigned ret = seed;
	seed = ((seed * 214013u) + 2531011u);
	return ret % 10000 + 1;
	}
	};
	// 신호분석
	int ites() {
	queue<int> q;
	int result = 0, queSum = 0;
	RNG rng;
	// n개의 신호를 순회한다.
	for (int i = 0; i < n; i++) {
	// 신호생성
	int newSignal = rng.next();
	q.push(newSignal);
	queSum += newSignal;
	// 큐에 들어있는 신호들의 합이 k이상이면 순서대로 신호 pop
	while (queSum >= k) {
	// 큐에 들어있는 신호들의 합이 k면 result++
	if (queSum == k)
	result++;
	queSum -= q.front();
	q.pop();
	}
	}
	return result;
	}
	int main() {
	int testcase;
	cin >> testcase;
	while (testcase--) {
	cin >> k >> n;
	cout << ites() << endl;
	}
	}

view raw algospot 외계 신호 분석 (문제 ID: ITES).cpp hosted with ❤ by GitHub

코드 원본: https://github.com/sbl133/JongmanBook/blob/main/19.%20QueueStackDeque/ITES.cpp

GitHub - sbl133/JongmanBook

댓글을 통한 코드리뷰, 질문, 지적 언제든 환영입니다!

reference: 프로그래밍 대회에서 배우는 알고리즘 문제해결전략2