[BOJ 20305 // C++] 피보나치와 수열과 쿼리

※ 글쓴이는 취미로 코딩을 익혀보는 사람이라 정확하지 않은 내용을 담고 있을 수 있다 ※

 

이번에 볼 문제는 백준 20305번 문제인 피보나치와 수열과 쿼리이다.
문제는 아래 링크를 확인하자.

https://www.acmicpc.net/problem/20305 

20305번: 피보나치와 수열과 쿼리

이 문제를 풀기 위해 관찰해야할 것은 다음 두 가지이다.

1) 모든 쿼리를 처리한 이후의 최종 결과만을 출력하면 된다. 또한, 이 문제에서 주어지는 쿼리는 순서를 바꿔서 계산해도 최종 결과가 변하지 않는다. (단순한 덧셈이므로)

2) 피보나치 수의 특징을 생각하여, 각 쿼리를 입력받아 시작점, 끝점에 1과 쿼리 구간길이에 대응되는 적절한 피보나치수를 구간의 끝에서 빼주는 것으로 미리 전부 업데이트를 하고 피보나치 점화관계를 이용하여 수열을 구해낼 수 있다.

 

아래는 제출한 소스코드이다.

#include <iostream>
using namespace std;
typedef long long ll;

ll fib[1000011];
ll arr[1000011];

int main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);

    fib[1] = fib[2] = 1;
    int N, Q; cin >> N >> Q;
    
    for (int i = 3; i <= 1000010; i++) {
        fib[i] = (fib[i - 1] + fib[i - 2])%1000000007;
    }

    while (Q--) {
        int x, y; cin >> x >> y;
        arr[x] += 1;
        arr[y + 1] -= fib[y - x + 2];
        arr[y + 2] -= fib[y - x + 1];
    }
    
    for (int i = 1; i <= N; i++) {
        cout << arr[i] << ' ';
        arr[i + 1] += arr[i-1] + arr[i];
        arr[i + 1] %= 1000000007;
        if (arr[i + 1] < 0) arr[i + 1] += 1000000007;
    }
}