Algospot ITES

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

문제에서 주어진 공식으로 배열을 미리 만든 다음에 결과를 구하면 쉽겠지만 입력값이 너무 많은 관계로 온라인 알고리즘(online algorithm)을 통해 문제를 풀어야합니다.

온라인 알고리즘은 전체 입력이 한꺼번에 주어지지 않아도 계산을 시작할 수 있는 알고리즘입니다.

난수 생성기 RNG를 만든 다음에 큐를 통해 여태까지 주어진 숫자들의 합을 구합니다.

반복문을 통해 난수를 큐에 입력하고 합을 구하는데 값이 초과하면 rear는 고정시키고 front를 한칸씩 앞으로 옮기면서 합을 다시 구하는 형식으로 결과를 구할 수 있습니다!

#include <iostream>

#include <queue>

using namespace std;

 

const int MOD = 10000;

 

int C, K, N;

 

//모든 숫자가 저장된 벡터 내에서 부분 수열 합이 k인 개수 구하는 경우

/*

int optimized(const vector<int> &signals, int k)

{

        int result = 0, tail = 0, rangeSum = signals[0];

       

        for (int head = 0;head < signals.size(); head++)

        {

                 //rangeSum이 k 이상인 최소의 구간을 만날 때까지 tail을 옮긴다

                 while (rangeSum < k && tail + 1 < signals.size())

                         rangeSum += signals[++tail];

                 if (rangeSum == k)

                         result++;

                 //signals[head]는 이 구간에서 빠진다

                 rangeSum -= signals[head];

        }

        return result;

}

*/

 

struct RNG

{

        unsigned seed;

        RNG() : seed(1983) //생성자

        {

        }

        unsigned next()

        {

                 unsigned result = seed;

                 seed = ((seed * 214013u) + 2531011u);

                 return result % MOD + 1;

        }

};

 

int countRanges(int k, int n)

{

        RNG rng; // 신호값을 생성하는 난수 생성기

        queue<int> range; // 현재 구간에 들어 있는 숫자들을 저장하는 큐

        int result = 0, rangeSum = 0;

 

        for (int i = 0; i < n; i++)

        {

                 // 구간에 숫자를 추가한다

                 int newSignal = rng.next();

                 rangeSum += newSignal;

                 range.push(newSignal);

 

                 // 구간의 합이 k를 초과하는 동안 구간에서 숫자를 뺀다

                 while (rangeSum > k)

                 {

                         rangeSum -= range.front();

                         range.pop();

                 }

 

                 if (rangeSum == k)

                         result++;

        }

        return result;

}

 

 

int main(void)

{

        cin >> C;

 

        for (int i = 0; i < C; i++)

        {

                 cin >> K >> N;

 

                 cout << countRanges(K, N) << endl;

        }

        return 0;

}

개발환경:Visual Studio 2017

지적, 조언, 질문 환영입니다! 댓글 남겨주세요~

참고: [프로그래밍 대회에서 배우는 알고리즘 문제해결전략]