[ALGOSPOT] 알고스팟 ITES 외계 신호 분석(C++, Python)

www.algospot.com

[ALGOSPOT] 알고스팟 ITES 외계 신호 분석

(C++, Python)

(글쓴날 : 2020.05.30)

 

---

* ALGOSPOT, 알고스팟 ITES 문제 C++, Python 언어 풀이입니다.

* 소스 코드의 저작권은 글쓴이에게 있습니다.

---

 

 

알고스팟 ITES 외계 신호 분석

---

1) 문제

문제 링크 : https://algospot.com/judge/problem/read/ITES

algospot.com :: ITES

---

2) 풀이 과정

* 시간 복잡도 : O(n)

 

특정 값들이 들어있는 수열이 주어질 때, 합이 K가 되는 부분 수열이 몇 개인지 구하는 문제입니다.

특이하게도, 이 문제는 다른 문제들과 달리 시작할 때 입력 값이 바로 주어지지 않으며, 주어진 규칙과 식을 통해 직접 입력 값을 생성해야 합니다.

이러한 방식을 온라인 알고리즘이라 하는데 문제에서 주어져야 할 입력값이 메모리 한도를 초과할 때 사용합니다.

 

저의 경우, 큐를 적용하였고, C++와 Python을 사용했습니다.

먼저, 첫 신호를 1983으로 초기화한 후 문제에서 주어진 규칙과 식을 통해 다음 신호값들을 구했습니다.

주어진 규칙을 해석하면 현재 신호는 항상 이전 신호 % 10000 + 1이며, 다음 신호로 넘어가기 전에 (이전 신호 * 214013 + 2531011) % 2³² 연산을 해주어야 합니다.

이렇게 구해진 신호들을 큐에 넣고 빼가며, 큐에 저장된 신호들의 합과 K를 비교해 문제를 해결했습니다.

단, Python의 경우 C++과 같은 로직인데도 불구하고 시간 초과가 발생합니다. (PyPy도 마찬가지입니다.)

---

3) 코드

 

* C++ 코드

#include <iostream>
#include <queue>
#include <cmath>
 
using namespace std;
 
int main(void)
{
    ios_base::sync_with_stdio;
    cin.tie(NULL);
    cout.tie(NULL);
 
    int C = 0;
    cin >> C;
 
    int K = 0, N = 0;
 
    while (C--)
    {
        long long prevSignal = 1983;
        int nowSignal = 0;
        int sumSignal = 0;
        int ans = 0;
        queue<int> q;
 
        cin >> K >> N;
 
        while (N--)
        {
            nowSignal = (int)(prevSignal % 10000 + 1);
            sumSignal += nowSignal;
            q.push(nowSignal);
 
            while (sumSignal > K)
            {
                sumSignal -= q.front();
                q.pop();
            }
 
            if (sumSignal == K)
                ans++;
 
            prevSignal = (prevSignal * 214013 + 2531011) % (long long)(pow(2, 32));
        }
 
        cout << ans << "\n";
    }
 
    return 0;
}

---

* Python 코드

from collections import deque
import sys
input = sys.stdin.readline
 
C = int(input())
 
for _ in range(C):
    K, N = map(int, input().split())
    dq = deque()
    prevSignal = 1983
    sumSignal = 0
    ans = 0
 
    for _ in range(N):
        nowSignal = prevSignal % 10000 + 1
        sumSignal += nowSignal
        dq.append(nowSignal)
 
        while sumSignal > K:
            sumSignal -= dq.popleft()
            
        if sumSignal == K:
            ans += 1
        
        prevSignal = (prevSignal * 214013 + 2531011) % (2 ** 32)
    
    print(ans)

---