[boj][c++] 구간 합 구하기 4 (구간합/시간초과/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

 

풀이 방법
합을 구해야 함  -> 구간합 사용
최대 10만 번의 합 -> 맨 처음에 한 번만 싹 구해놓고 우려먹기!
시간 초과 조심 -> cin.tie(0)->sync_with_stdio(0); 을 사용해 입출력 속도 높이기

 

#include <bits/stdc++.h>
using namespace std;

int N, M;
int arr[100001];
int dp[100001]={0};

int main(){
    cin.tie(0)->sync_with_stdio(0);
    int x, y;
    cin >> N >> M;
    for(int i=0; i<N; i++) cin >> arr[i];
    dp[0] = arr[0];
    for(int i=1; i<N; i++){
        dp[i] = dp[i-1] + arr[i];
    }
    for(int i=0; i<M; i++){
        cin >> x >> y;
        cout << dp[y - 1] - dp[x - 2] << '\n';
    }
}

 

기억하고 넘어갈 점
1. 구해야 하는 것이 몇 번인지 횟수 확인하고 많을 경우, 최소화 방안 생각하기
     - 맨 처음 한 번만 계산해서 싹 저장해놓기 등등
2. cin.tie(0)->sync_with_stdio(0); 항상 사용해서 입출력 속도 높이기
    - C++에서 cin과 cout은 기본적으로 tie(연결)되어 있음
    - cout으로 출력한 후에 cin으로 입력 받으면 그사이에 버퍼가 자동으로 비워짐
    - 따라서 cin과 cout의 동기화를 끊어서 입출력의 효율을 높임