#[C++] 11659 - 구간 합 구하기 4

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

---

문제

수 N개가 주어졌을 때, i번째 수부터 j번째 수까지 합을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 수의 개수 N과 합을 구해야 하는 횟수 M이 주어진다. 둘째 줄에는 N개의 수가 주어진다. 수는 1,000보다 작거나 같은 자연수이다. 셋째 줄부터 M개의 줄에는 합을 구해야 하는 구간 i와 j가 주어진다.

출력

 

총 M개의 줄에 입력으로 주어진 i번째 수부터 j번째 수까지 합을 출력한다.

제한

• 1 ≤ N ≤ 100,000
• 1 ≤ M ≤ 100,000
• 1 ≤ i ≤ j ≤ N

---

#include <iostream>

using namespace std;
int main() {
    ios_base::sync_with_stdio(false);
    cout.tie(NULL);
    cin.tie(NULL);
    
    int n,m;
    cin >> n >> m;
    int arr[n+1];
    arr[0]=0;
    for(int i=1; i<=n; i++) {
        int a=0;
        cin >> a;
        arr[i] = arr[i-1]+a;
    }
    
    for(int k=0; k<m; k++) {
        int i=0, j=0;
        cin >> i >> j;
        cout << arr[j]-arr[i-1] << "\n";
    }
    return 0;
}

---

얼핏보면 쉽지만 시간 초과를 유의해야함.

그래서 반복문을 최소한으로 사용하려고 했음. O(1)이 나와야하므로,,

입력받자마자 바로 배열에 누적합으로 넣어버리고 했는데도 시간초과가 나서 찾아보니 c++는 i/o에서 많은 시간을 쓴다고 해서

맨 위에
    ios_base::sync_with_stdio(false);
    cout.tie(NULL);
    cin.tie(NULL);
위 코드를 넣어 시간을 단축하고자 했답니다..

outofbounds 에러도 많이 나서 for문도 하나하나 뜯어서 살펴보고 수정했다.

웩스바리