[백준] 11659번 : 구간 합 구하기 4

---

🔗 문제 링크

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

11659번: 구간 합 구하기 4

👩‍💻 코드

#include <iostream>
using namespace std;

int main(){
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
    
    int N = 0;
    int M = 0;
    cin >> N >> M;
    
    int sum[100001] = {};
    
    for(int n=1; n<=N; n++){
        int temp;
        cin >> temp;
        sum[n] = sum[n-1] + temp;
    }
    
    int i = 0;
    int j = 0;
    
    for(int n=0; n<M; n++){
        cin >> i >> j;
        cout << sum[j] - sum[i-1] << "\n";
    }
}

✏️ 풀이

핵심은 구간합이라는 알고리즘이다!

무려 시간 복잡도를 O(N)에서 O(1)로 줄일 수 있다.

그리고 시간 단축을 위한 C++ 팁!

종종 시간 초과를 할 경우 활용하자.

 

ios::sync_with_stdio(false);

C의 stdio와 C++의 iostream의 동기화 비활성화, C++ 독립 버퍼 사용으로 수행 속도가 빨라지는 효과가 발생한다.

cin.tie(NULL); cout.tie(NULL);

하나로 묶인 두 스트림을 풀어 cin을 수행하기 전 기본적으로 cout 출력 버퍼를 지우는 작업을 수행하는 과정을 생략하여 속도가 빨라지는 효과가 발생한다.

 

풀이와 팁의 출처는 Do it! 알고리즘 코딩 테스트 C++편에서 발췌하였습니다.