[ 백준 26087 ] 피보나치와 마지막 수열과 쿼리 : C++ 풀이
Contents
문제 접근
오프라인 쿼리라는 개념을 알고 접근해보도록 합시다.
오프라인 쿼리란 간략히 말해서, 쿼리의 전체 적용 결과 값만 알고 싶을 때 사용하는 전략으로, 쿼리의 순서를 모두 받은 뒤, 역순으로 처리할 때, 중복처리가 되지 않는 경우 그 점을 이용하는 전략입니다.
이 점을 이용해서 문제를 풀 수 있습니다.
솔루션
단, 위 개념을 알아도, 칠해져있는지 일일이 매 역순 쿼리마다 확인해나가다 보면 시간초과하기 마련입니다.
따라서 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]] << ' ';
}
}