[ 백준 26087 ] 피보나치와 마지막 수열과 쿼리 : C++ 풀이

문제 접근

오프라인 쿼리라는 개념을 알고 접근해보도록 합시다.

오프라인 쿼리란 간략히 말해서, 쿼리의 전체 적용 결과 값만 알고 싶을 때 사용하는 전략으로, 쿼리의 순서를 모두 받은 뒤, 역순으로 처리할 때, 중복처리가 되지 않는 경우 그 점을 이용하는 전략입니다.

이 점을 이용해서 문제를 풀 수 있습니다.

솔루션

단, 위 개념을 알아도, 칠해져있는지 일일이 매 역순 쿼리마다 확인해나가다 보면 시간초과하기 마련입니다.

따라서 space[1 to N] 라는 이름의 배열을 생성하여 현재 위치를 기록해도 되는지, 그게 아니라면 다음 위치는 어디가 되는지를 기록해두어야합니다.

이를 구현한 방법은 분리집합에서의 find() 와 같습니다.

일단 매 쿼리에서 주어진 l 과 r 구간에서, 우리가 칠했던 모든 지역의 space[] 값을 r + 1로 설정해둡시다.

우리가 칠하는 지역의 space[i] 값이 i가 아닌 경우, 언급한 find() 함수를 통해 재귀적으로 호출하며 space[] 값을 갱신해나가면 최적화가 가능합니다.

소스코드

#include<iostream>
#include<vector>
#include<utility>
using namespace std;

int space[1000001]; // 1 to 1m
int fibo[1000001]; // fibo value
int ind[1000001]; // answer which indicates index of fibo value.
const int MOD = 1000000007;

int find(int t) {
	if (space[t] == t) return t;
	return space[t] = find(space[t]);
}


int main() {
	cout.tie(0); cin.tie(0)->sync_with_stdio(0);

	fibo[1] = space[1] = 1;
	fibo[2] = space[2] = 2;
	
	for (int i = 3; i <= 1000000; ++i) {
		fibo[i] = fibo[i - 1] + fibo[i - 2];
		fibo[i] %= MOD;
		space[i] = i;
	}
	
	
	int n, q; cin >> n >> q;
	vector<pair<int,int>> query;
	space[n + 1] = n + 1;

	for (int i = 0; i < q; ++i) {
		int l, r; cin >> l >> r;
		query.push_back({l, r});
	}

	for (int i = query.size() - 1; i >= 0; --i) {
		int l = query[i].first;
		int r = query[i].second;
		int next = space[l];
		while (next <= n && next <= r) {
			next = find(next);
			if (next > r) break;
			int idx = next - l + 1;
			ind[next] = idx;
			space[next] = r + 1;
			next++;
		}
	}
	for (int i = 1; i <= n; ++i) {
		cout << fibo[ind[i]] << ' ';
	}
}