[알고리즘 문제해결전략] ITES - 외계 신호 분석

[생각의 흐름]

1. 수열의 앞에서 부터 하나하나 더하면서 수열의 연속 된 특정 범위 내에서 K값을 찾는다.

2. 수열이 연속해야하기 때문에 맨 앞의 수열은 빼고 맨 뒤의 수열은 넣는 방법 두 가지가 있다.

3. K보다 값이 크면 맨 앞의 수열을 빼고(Pop) K보다 값이 작으면 맨 뒤에 수열을 추가한다(Push).

4. K와 값이 같으면 cnt++;

 

* 맨 처음에는 수열(signal A)를 배열에 초기화 하여 사용하려 했으나 메모리 초과가 발생하여 그때 그때 값을 만들어 내는 방식을 택함.

/* https://www.algospot.com/judge/problem/read/ITES */

#include <stdio.h>
#include <queue>
#include <cmath>

using namespace std;

const long MOD = pow(2, 32);

long generateNextA(long prevA)
{
    long nextA = (prevA * 214013 + 2531011) % MOD;
    return nextA;
}

int main(void)
{
    int C;
    scanf("%d", &C);
    while (C--)
    {
        queue<int> qu;
        long A = 1983;
        int K, N;
        int cnt = 0;
        int sum = 0;
        int i = 1;

        scanf("%d %d", &K, &N); 
        while (i <= N)
        {
            if (sum < K)
            {
                int signal = A % 10000 + 1;
                qu.push(signal);
                sum += signal;
                i++;
                A = generateNextA(A);
                continue;
            }

            if (sum == K)
                cnt++;

            sum -= qu.front();
            qu.pop();

        }
        printf("%d\n", cnt);
    }

    return 0;
}