[BOJ] #11659 구간 합 구하기 4

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

11659번: 구간 합 구하기 4

---

문제 자체는 간단한 문제이지만, 문제를 보자마자 딱 떠오른 그 방법으로 풀면 무조건 시간초과에 걸리는 문제이다.

보자마자 딱 떠오른 방법이란, 일단 주어지는 배열을 입력받고, 이후에 입력되는 인자들로 하여금 배열에 접근하여 부분 합을 생으로 구하는 방법일텐데,,, 문제 자체의 시간 제한이 1초인데 비해 해당 매커니즘의 wosrt-case가 100억이다... M번 반복되는 반복문 안에서 배열의 인덱스를 N번 탐색하는, 즉 O(N^2)의 시간복잡도를 가지고 있기 때문에 이 방법으로는 절대 문제를 해결할 수 없다.

이 문제의 키 포인트는 주어지는 배열을 그대로 배열화 하지않고, 입력이 들어올때마다 계속 해서 부분 합을 저장하는 배열을 따로 만들어 입력과 동시에 부분 합을 계산할 수 있도록 하는것이다. 이렇게 하면, 배열 입력이 끝난 시점에 이미 모든 부분합을 접근해서 불러올 수 있게된다. 그럼 그 이후에 부분합을 계산할 시작지점과 끝지점을 입력받고, 미리 만들어둔 부분합 배열에서 조건에 맞게 찾아주면 해결되는 것이다.

필자 또한 두번째 방법을 생각해내기 전에는 시간초과를 계속 띄우다가 매커니즘을 수정하고 해결할 수 있었다. 이때 자료구조는 성능향상을 위해 vector 보다는 정적배열을 사용했으며, iostream 입출력 성능을 개선시키기 위한 코드를 따로 추가하여 해결했다.

---

#include <iostream>

using namespace std;

int tmp;
int sum = 0;
int arr[100005];

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

    int N,M;
    cin >> N >> M;

    for (int i=1; i<=N; i++) {
        cin >> tmp;
        sum += tmp;
        arr[i] = sum;
    }

    while (M--) {
        int a,b;
        cin >> a >> b;

        int total = arr[b] - arr[a-1];
        cout << total << '\n';
    }

    // vector<int> v;
    // for (int i=0; i<N; i++) {
    //     int a;
    //     cin >> a;

    //     v.push_back(a);
    // }

    // while (M--) {
    //     int a,b;
    //     cin >> a >> b;

    //     int total = 0;
    //     a--; b--;

    //     for (int j=a; j<=b; j++) {
    //         total += v[j];
    //     }

    //     cout << total << '\n';
    // }

    return 0;
}

주석 처리된 부분이 시간초과가 났던 vector를 사용한 O(N^2)짜리 코드이다...

시간 초과 두번..