🚀 [ITES] 문제 😊😊😊😊😊
수환이는 외계에서 날아오는 전파를 연구하는 범세계 대규모 프로젝트, ITES@home에 참가하고 있습니다. 외계에서 날아오는 전파는 전처리를 거쳐 각 숫자가 [1,10000] 범위 안에 들어가는 자연수 수열로 주어지는데, 이 전파가 과연 단순한 노이즈인지 아니면 의미 있는 패턴을 가지고 있는 것인지를 파악하고 싶습니다. 수환이는 전파의 부분 수열 중에 합이 K인 것이 유독 많다는 것을 눈치챘습니다. 부분 수열이란 연속된 수열의 일부를 말합니다. 예를 들어 수열 {1,4,2,1,4,3,1,6} 에서 합이 7 인 부분 수열은 모두 5개 있습니다. {1,4,2} , {4,2,1} , {2,1,4}, {4,3}, {1,6} 이 부분 수열들은 서로 겹쳐도 된다는 데 유의합시다.
K가 외계인에게 의미 있는 숫자일까요? 수환이의 가설을 확인하기 위해, 길이 N인 신호 기록이 주어질 때 합이 K인 부분 수열이 몇 개나 있는지 계산하는 프로그램을 작성하세요.
💡 입력생성
입력의 크기가 큰 관계로, 이 문제에서는 신호 기록을 입력받는 대신 다음과 같은 식을 통해 프로그램 내에서 직접 생성합니다.
- A[0] = 1983
- A[i] = (A[i-1] * 214013 + 2531011) % \(2^{32}\)
이 때 i(1 <= i <= N)번째 입력 신호는 A[i-1] % 10000 + 1입니다. 문제의 해법은 입력을 생성하는 방식과는 아무 상관이 없습니다. 이 규칙에 따르면 첫 5개의 신호는 각각 1984, 8791, 4770, 7665, 3188입니다.
🔑 [풀이]
규칙에 맞는 난수를 생성하는 RNG 구조체를 생성한후, n번만큼의 난수를 받아온다.
이후 큐를 이용하여 난수를 저장하고 만약 이떄까지의 난수들의 합이 k를 초과하면 큐의 head 부분을 제거하고 tail은 유지한다.
조건인 난수들의 합이 k를 만족하면 결과를 더해준다\
코드참고.
⌨️ 입력
입력 파일의 첫 줄에는 테스트 케이스의 수 C (1 <= C <= 20)가 주어지고, 그 후 C 줄에 각 2개의 정수로 K(1 <= K <= 5,000,000) 과 N(1 <= N <= 50,000,000) 이 주어집니다.
🖥 출력
각 테스트 케이스마다 한 줄에 첫 N 개의 신호 중 합이 K 인 구간의 수를 출력합니다.
🖱 입력 예제
3
8791 20
5265 5000
3578452 5000000
💻 출력 예제
1
4
1049
💎 전체 코드는 다음과 같습니다.
//
// ITES.cpp
// AALGGO
//
// Created by inhyeok on 2021/11/30.
//
#include <iostream>
#include <fstream>
#include <queue>
using namespace std;
ifstream fin("ITES.txt");
const int MOD = 10000;
// 신호 생성기
struct RNG
{
unsigned seed;
RNG() : seed(1983) {}//생성자
unsigned next()
{
unsigned result = seed;
seed = ((seed * 214013u) + 2531011u);
return result % MOD + 1;
}
};
int countRange(int k, int n){
RNG rng; // 신호값을 생성하는 난수 생성기
queue<int> range; // 현재 구간에 들어 있는 숫자들을 저장하는 큐
int ret = 0, rangeSum = 0;
for(int i=0; i<n; i++){
// 새신호를 받아온다
int newSignal = rng.next();
rangeSum += newSignal;
range.push(newSignal);
while(rangeSum > k){
rangeSum -= range.front();
range.pop();
}
if(rangeSum == k) ret++;
}
return ret;
}
int main(){
int test_case;
fin >> test_case;
for(int test=0; test<test_case; test++){
int K, N;
fin >> K >> N;
cout << countRange(K,N) << endl;
}
}
Comments