[Algospot] 알고스팟 외계 신호 분석 문제풀이(ITES)

핵심은 큐를 이용하여 수열의 합이 K인 경우를 순차적으로 탐색한다는 것과, 배열을 쓰면 안된다는 것(용량초과)

배열로 모든 신호를 저장했다가 런타임오류 발생해서 순차적으로 탐색하면서 값을 저장함(unsigned int 배열 5천만개는 65535kb를 초과함)

또한 unsigned int를 이용해서 계산식에서의 % 2^32를 날리는 것도 핵심이었던거 같음

수행시간 : 5160ms

 

#include<iostream>
#include<queue>
using namespace std;
 
/*
<문제> - 시간 15초, 메모리 65536kb
수열이 주어지는데, 부분수열의 합이 K인 경우의 수를 구하기
부분수열은 연속된 수열의 일부로, 서로 겹쳐도 됨
신호생성 식 주어짐(입력이 큰 관계로)
A[0]=1983
A[i] = (A[i-1] * 214013 + 2531011) % 2^32
이 때 i(1~N)번째 입력신호는 A[i-1] % 10000 + 1
 
<입력>
C    테스트케이스(<=20)
K N(500만, 5천만)
 
<출력>
각 테스트케이스마다 N개의 신호중 합이 K인 구간의 수 출력
 
 
*/
//unsigned int A[50000001];    //수열
//unsigned int signal[50000001];    //수열
 
int main() {
    int C; cin >> C;
    while (C--) {//testcase
        int K, N; cin >> K >> N;
        queue<unsigned int> finder;    //여기에 넣어가면서 찾을거
 
        int flag = 0;    //현재 signal 위치
        int sum = 0;    //현재 합
        int count = 0;    //합이 K인 경우의 수
        unsigned int A = 1983, signal = 1984;    //현재 A값, signal값
        //A[i] = ((A[i - 1] * 214013 + 2531011));
        //signal[i] = A[i - 1] % 10000LL + 1;
 
        while (flag <= N) {
 
            if (sum == K) {    //합이 K인경우
                count++; flag++;
                signal = A % 10000LL + 1; A = (A * 214013 + 2531011);
                finder.push(signal); sum += signal;
            }
            else if (sum > K) {    //합이 초과한경우
                sum -= finder.front(); finder.pop();
            }
            else if (sum < K) {    //합이 모자란 경우
                flag++;
                signal = A % 10000LL + 1; A = (A * 214013 + 2531011);
                finder.push(signal); sum += signal;
            }
        }
        cout << count << endl;
    }
    return 0;
}