[백준] 2900번: 프로그램 - C++

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

 

문제 구현을 그대로 구현하면 답을 얻을 수 있다. 하지만 시간복잡도가 굉장히 커지기 때문에 시간 초과를 받게 된다. something 함수를 호출 하는 과정에서 $O(KN)$, 합을 구하는 과정에서 $O(QN)$의 시간복잡도가 필요하다. 하지만 $N, K, Q$가 최대 $10^6$까지 커질 수 있으니 시간 제한을 만족시킬 수 없다.

구간 합

구간의 합은 누적합을 사용하면 $O(1)$에 구할 수 있다. 따라서 누적합을 적용하면 $O(Q)$에 처리가 가능하다.

 

something 호출

매번 입력이 주어질 때마다 갱신하면 연산을 여러 번 반복하게 된다. 예를 들어 첫번째 원소는 항상 1씩 증가한다. 따라서 매번 업데이트 하지 말고 각 입력이 주어진 횟수를 저장해 두었다가 한번에 갱신하면 더 빠르게 처리할 수 있다.

 

#include <iostream>
#include <map>
#include <algorithm>

using namespace std;

long long a[1000000];

int main() {
    cin.tie(nullptr);
    cout.tie(nullptr);
    ios_base::sync_with_stdio(false);

    int n, k;
    cin >> n >> k;

    map<int, int> cache;
    while (k--) {
        int x;
        cin >> x;
        cache[x]++;
    }

    for (auto [nxt, cnt] : cache) {
        int i = 0;
        while (i < n) {
            a[i] += cnt;
            i += nxt;
        }
    }

    long long sum[n + 1];
    sum[0] = 0;
    for (int i = 1; i <= n; i++)
        sum[i] = sum[i - 1] + a[i - 1];

    int m;
    cin >> m;
    while (m--) {
        int l, r;
        cin >> l >> r;
        cout << sum[r + 1] - sum[l] << '\n';
    }
}