알고스팟(algospot) ITES - 외계 신호 분석

쉬운줄 알았는데, 걸림돌이 많았다.

먼저 seed를 만듣는것에서 실수가 있었다. unsigned long long형을 통해 시드를 만들었는데

1번케이스만 나오고 나오질 않았다. 종만북을 보고, seed구하는 곳을 보았고 감탄쓰!

unsigned int로 선언하여 그냥 곱하고 더하면 자동으로 %2^32가 된다...

그럼 나는 어느곳에서 틀렸을까?

바보같이 2^32가 

unsigned long long MOD = (1ULL << 31);

요거라 생각했다...32번째 비트를 세팅해야겠다는 생각에 사로잡혀있었다.

사실 2^32는 33번째 비트를 세팅해야 값이 나오고 이값을 %하게되면 1~32비트의 값이 되는 것이었다.. 바보였다. 왜몰랐지.. 사실 지금도 약간 헷갈린다. 2^32은 int형으로 표현이 불가능하다는 것을 기억해야겠다.

다음 실수는 list였다. list를 이용하여 푸쉬는 뒤를 해주었고, pop은 앞을해주었다. 사실 pop은 무조건 앞에서만 일어나기 때문에 큐 자료구조가 맞다. 데큐에 꽂혀있던 것 같다. 큐가 생각이 나질 않았다. 실제 list를 쓰니 시간초과가 발생했고, 큐로 고치니 AC를 받았따. 큐는 배열로 구현되어있고 리스트는 동적할당이 들어가 속도 차이가 나는 것 같았다. (아님 말구..)

무튼 적합한 자료구조를 생각하는 연습 및 실수를 줄이는 연습을 계속 해야겠다.

#include <iostream>
#include <queue>
using namespace std;
queue<int> q;
int main() {
    int T;
    scanf("%d", &T);
    while(T--){
        unsigned seed = 1983u;
        int K, N;
        scanf("%d %d", &K, &N);
        int sum = 0;
        int cnt = 0;
        for(int i = 1; i <=N; i++){
            int num = (int)(seed% 10000 + 1);
            sum += num;
            q.push(num);
 
 
            while(sum >= K && !q.empty()){
                if(sum  == K){
                    cnt++;
                }
                sum -= q.front();
                q.pop();
            }
 
            seed = seed * 214013u + 2531011u;
        }
        printf("%d\n", cnt);
        while(!q.empty()) q.pop();
 
    }
 
 
    return 0;
}