(출처) https://algospot.com/judge/problem/read/ITES
그냥 세기만 해도 되지 않을까?
최대 5천만 길이의 수열이 주어졌을 때 해당 수열로 만들 수 있는 합이 K가 되는 부분 수열의 개수를 모두 세는 문제.
얼핏 보면 5천만이나 되는 길이의 수열을 전부 탐색해야 한다는 압박감 때문에 이걸 시간 안에 계산할 수 있을까라는 생각이 들었지만, 합이 K가 되는 부분수열만 세주면 된다는 조건을 생각하면 굉장히 문제가 단순해지는 것을 알 수 있다.
수열에서 특정 원소를 기준으로 해당 원소를 맨 앞에두고 시작했을 때, 합이 K가 되는 부분수열은 단 1개밖에 존재하지 않는다. 따라서 합이 K가 되는 부분수열의 최대개수는 수열 원소의 개수이며 총 5천만개이다.
그렇다면 수열의 첫 번째 원소부터 시작해 가장 K와 근접하게 부분수열을 형성한 뒤, 그다음부터는 첫 번째 원소를 삭제하고 부분수열의 마지막 원소에다 다음 차례의 원소를 1개씩 추가해주며 합이 K가 되는 수열이 있는지 하나씩 판단해 나간다면 O(N)의 시간복잡도 즉 5천만 번의 계산반복으로 충분히 문제를 해결할 수 있다.
근데 그냥 세기만 하면 안 되네
로직을 짜고 난 뒤 생각보다 풀만하다고 생각한 것은 내 착각이었다. 해당 로직대로라면 분명 시간초과는 나지 않는다. 하지만 메모리 초과가 난다.
5천만 길이의 int형 배열을 선언하게 되면 대충 2억바이트 가량의 공간을 할당하게 되는데, 2억 바이트는 200 메가바이트 정도이므로 문제의 64MB 이하의 메모리만 사용하라는 제한에 걸리고 만다.
지금까지 알고리즘 문제를 풀면서 시간제한에서 걸리지는 경우는 많았어도 메모리 제한으로 발목을 잡힌 것은 이번이 처음이었다.
저장하지말고 만들면서 풀기
주어진 수열을 모두 저장하고 계산을 진행하는 것은 불가능하므로 차라리 저장을 하지 않고 문제를 풀 수 있는지 생각해 보았다.
부분수열의 첫 번째 원소를 가리키는 포인터를 기준으로 다음 원소를 계산해서 곧바로 첫 번째 원소와 더해준다. 이때 원소가 더해진다는 것은 부분수열에 원소가 계속 추가된다는 뜻이므로, 원소가 더해질 때마다 부분수열의 마지막 원소를 가리키는 포인터를 계속 갱신해 준다. 이 행위를 원소의 합이 K와 같거나 커질 때까지 반복한다.
만약 합이 K보다 커졌을 경우 저장해놓은 첫 번째 포인터를 이용하여 첫 번째 원소의 크기만큼 원소들의 합에서 빼준 뒤, 다시 새로운 첫 번째 원소를 가리키도록 첫 번째 포인터를 갱신한다. 첫 번째 원소를 가리키는 포인터가 수열의 마지막 원소를 가리킬 때 까지 반복한다.
위의 로직에서는 포인터라고 표현했지만 사실은 int형 변수 2 개에 첫 번째와 마지막 원소의 값을 담고서 이 값을 매번 갱신해 주면서 추상적으로 포인터같이 행동하게끔 하는 구현이다. 이렇게 하면 배열에 수를 따로 저장하지 않고도 첫 번째를 원소를 가리키는 포인터의 N 번 탐색, 마지막 원소를 가리키는 포인터의 N 번 탐색, 총 2N 번의 탐색이 필요하게 되고 결국 O(N)의 시간복잡도로 메모리를 많이 사용하지 않고도 충분히 구현이 가능하게 된다.
코드
#define _CRT_SECURE_NO_WARNINGS
#include <iostream>
#include <algorithm>
#include <string>
using namespace std;
int k, n;
/*
int signalMaking(int n){
int s_size = signal.size();
if (n <= s_size) return 0;
for (int i = 0; i < n - s_size; i++) {
A = ((A * 214013) + 2531011) % 4294967296;
signal.push_back(A % 10000 + 1);
}
return 0;
}
*/
int signalMaking(unsigned long long *num){
*num = (*num * 214013 + 2531011) % 4294967296;
return (*num) % 10000 + 1;
}
int ites() {
unsigned long long first_Rnum = 1983;
unsigned long long second_Rnum = 1983;
int first[2] = { 1984, 1 };
int last[2] = { 1984, 1 };
int sum = 1984;
int ret = 0;
//last가 맨끝인데 sum이 k보다 작은 경우 더이상의 진행을 그만두고 ret을 반환
while( !(last[1] == n && sum < k) ) {
//first 포인터가 last를 지나쳐버린 경우 last를 다시고정
if (first[1] > last[1]) {
last[0] = first[0];
last[1] = first[1];
second_Rnum = first_Rnum;
}
if (sum >= k) {
if (sum == k) ret++;
first[1]++;
sum -= first[0];
first[0] = signalMaking(&first_Rnum);
if (sum == 0) sum += first[0];
}
else {
last[1]++;
last[0] = signalMaking(&second_Rnum);
sum += last[0];
}
// 기저사례 first가 범위를 벗어난 경우 진행을 그만두고 ret을 반환
if (first[1] == n + 1) break;
}
return ret;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(NULL);
cout.tie(NULL);
int testcase;
cin >> testcase;
while (testcase--) {
cin >> k >> n;
int first[2] = {1984, 1};
int last[2] = {1984, 1};
int ret = ites();
cout << ret << "\n" ;
}
return 0;
}기억하고 싶은 점
애당초 메모리를 사용하지 않기 위해서 자료구조를 이용하지 않는데 어째서 이 문제가 자료구제 파트로 분류되어 있는지가 의문이었다. 책의 해답을 보니 아예 자료구조를 이용하지 않는 것은 아니고 크기가 작은 큐에 원소를 계속해서 추가 및 삭제해 주는 방식으로 진행하더라.
해당 방식 또한 문제를 풀면서 나도 잠깐은 생각해 봤었는데 만약 모든 입력 신호가 1로 구성되고 K가 5천만이 된다면 결국 5천만 개의 원소를 또 저장하는 셈이 되지 않을까 해서 포기하고 아예 원소를 저장하지 않는 방식으로 방향을 정했다.
입력 신호가 충분히 크다면 부분수열의 원소 합이 금방 K에 도달하게 돼서 일부 원소를 저장하면서 진행하더라도 메모리를 적게 사용할 수 있겠지만 거기까지는 계산하지 않았다.
온라인, 오프라인 알고리즘에 대한 설명도 흥미로웠다.
