19.6_외계 신호 분석_ITES

문제 설명

 

algospot.com :: ITES

• 전파는 각 숫자가 [1, 10000] 범위에 들어가는 자연수 수열로 주어진다.
• 부분 수열의 합인 K(1 <= K <= 5,000,000), 배열의 크기 N(1 <= N <= 50,000,000)이 주어진다.
• 입력되는 전파의 배열은 직접 구하는데, 아래 식으로 구할 수 있다.
  • A[0] = 1983
  • A[i] = (A[i-1] * 214013 + 2531011) % 2^32
• 그리고 전파에 사용하는 숫자는 A[i-1] % 10000 + 1 으로 사용한다.

=>  전파의 부분 수열 중에 합이 K인 부분 수열의 개수를 출력하기

 

문제 풀이

Deque를 이용해 K 이하의 부분집합의 합 유지하기

이 문제는 N이 너무 크기 때문에 미리 배열에 저장해두고 부분 집합을 구할 수 없다.

그러므로 다른 방법을 써야 한다.

 

숫자가 하나씩 더해질 때마다 더해진 총합이 K보다 커지는 순간, 뒤에 어떤 숫자를 더해도 K와 같아질 수는 없다.

따라서 먼저 더해졌던 숫자들을 빼서 총합이 K보다 작거나 같도록 유지하고

뒤로 가면서 새로운 요소를 더하면 K와 같아지는 부분집합들을 구할 수 있다.

 

따라서 앞뒤로 요소를 넣고 빼고 할 수 있는 자료구조인 Deque를 활용해서

현재 더해진 부분집합 요소들만 저장한 상태로 N개의 숫자를 확인하였다.

 

 

문제 풀이 코드

#include <iostream>
#include <deque>

using namespace std;

long long pow32 = 4294967296;
long long signal = 1983;

int getNextNum() {	// 다음 숫자 만들기
	long long num = signal % 10000 + 1;
	signal = (signal * 214013LL + 2531011LL) % pow32;
	return num;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	int C;
	cin >> C;
	for (int tc = 1; tc <= C; ++tc) {
		int K, N, sum = 0, ans = 0;
		deque<int> dq;
		signal = 1983;
		cin >> K >> N;
		for (int i = 0; i < N; ++i) {
			int num = getNextNum();	// 다음 숫자 찾기
			dq.push_back(num);
			while(sum > K) {	// K보다 작아질 때까지 앞의 요소 빼기
				deque<int>::iterator iter = dq.begin();
				sum -= *iter;
				dq.pop_front();
				if (sum == K)	// K와 같은지 비교
					++ans;
			}
			sum += num;		// 뒤의 요소 더하기
			if (sum == K) {		// K와 같은지 비교
				++ans;
			}
		}
		cout << ans << endl;
	}

	return 0;
}