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

출처: https://www.algospot.com/judge/problem/read/ITES

 Input 

3

8791 20

5265 5000

3578452 5000000

 

 Output 

1

4

1049

 

구간의 길이를 1..N까지 모든 경우에 대한 구간합이 K인지 확인하는 경우 TLE 발생

Greedy하게 접근하여 최적화할 필요가 있습니다.

 

접근

ex) [1 4 2 1 4 3 1 6]에서 구간합 K = 7을 찾습니다.

* 구간합의 시작점인 [head]를 중심으로 접근

 

1 + 4 + 2 = 7로, 적절한 구간입니다. 여기서 tail을 우측이동 이동해봤자 

구간합은 증가하여 구간합 > 7이 됩니다.

즉, head를 우측으로 이동하여 구간의 범위를 줄여야 합니다.

 

여기서 눈여겨볼 점은 tail의 탐색 위치입니다.

tail도 기존 위치에서 + 1부터해서 적절한 구간을 탐색하면 됩니다.

 

시뮬레이션

구간합 4 + 2 + 1 = K이므로 head 우측 이동

구간합 2 + 1 < K 되므로 tail 우측 이동

 

구간합 4 + 2 + 1 = K이므로 head 우측 이동

구간합 2 + 1 < K 되므로 tail 우측 이동

 

구간합 1 + 4 + 3 > K이므로 head 우측 이동

구간 범위를 줄여야 하기 때문입니다.

 

구간합 4 + 3 = K 되었으므로 head 우측 이동

구간합 3 < K가 되므로 tail 우측 이동

 

구간합 3 + 1 + 6 > K 이므로 head 우측 이동

 

구간합 1 + 6 = 7 이므로 head 우측 이동

 

head가 모든 원소를 탐색했으므로 종료.

 

실제 코드에서는 모든 원소를 메모리 할당하지 않고 Queue 이용.

① 특정 구간 합 < K

▷ Queue(구간)에 새로운 숫자 추가

    (끝점tail 우측 이동하여 구간 길이 증가) 

 

② 특정 구간 합 > K

▷ Queue(구간)에서 숫자 제거

    (시작점head 우측 이동하여 구간 길이 감소) 

 

③ 특정 구간의 합 = K

▷ 시작점을 기준으로 더 이상 숫자를 추가할 이유가 없으므로

    구간에서 숫자를 제거한 다음 새로운 숫자 추가

     (시작점 head와 끝점tail 우측 이동하여 구간 길이 유지)

---

#include <iostream>
#include <queue>
using namespace std;
 
const int MOD = 10000;
struct RNG {
    unsigned signal;
    // 문제 입력에 따라 초기값 = 1983 (생성자)
    RNG() : signal(1983) {}
    unsigned next() {
 
        //현재 신호를 10000으로 나눈 나머지에 1을 더해서 출력신호 생성
        unsigned out = signal % MOD + 1;
 
        //다음 신호 생성
        signal = (signal * 214013u + 2531011u);
        return out;
    }
};
 
int countRanges(int K, int N) {
    RNG rng; // 난수 생성기
    queue<int> range; // 현재 구간에 들어 있는 숫자들을 저장하는 큐
    int answer = 0, rangeSum = 0;
 
    for (int i = 0; i < N; i++) {
        // 구간에 숫자 추가
        int newSignal = rng.next();
        rangeSum += newSignal; // 부분합
        range.push(newSignal);
 
        // 부분합(구간의 합)이 K보다 크면 Queue에서 앞의 숫자제거
        while (rangeSum > K) {
            rangeSum -= range.front();
            range.pop();
        }
 
        // 부분합이 K와 같은지 확인(현재 부분합은 작거나 같습니다.)
        // 적은 경우 다음 신호(숫자)를 추가하게됩니다.
        if (rangeSum == K)
            answer++;
    }
    return answer;
}
 
int main() {
    int C;
    cin >> C;
    while (C--) {
        int K, N;
        cin >> K >> N;
        cout << countRanges(K, N) << endl;
    }
}