[백준(BOJ)] 11659번 : 구간 합 구하기 4 - C++[CPP]

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

11659번: 구간 합 구하기 4

---

⊙ 문제

⊙ 입력

⊙ 출력

⊙ 예제 입출력

⊙ 알고리즘 분류

• 누적 합

 

---

 

⊙ 문제 접근 과정

 

누적 합 문제다.

 

처음엔 구현으로 풀라고 했다. 이중 for문을 사용하니 시간 복잡도가 O(N^2)이고 N과 M이 100,000까지라 시간 초과를 만날 수 있었다.

 

누적 합 문제의 해결법은 값을 배열에 넣고, 그 배열의 값들을 누적합 값으로 갱신시켜주어 index로 접근하여 구해주면 된다.

---

 

⊙ 문제 풀이

 

#include <iostream>

using namespace std;
#define MAX 100001

int N, M;
int arr[MAX];

int main() {
    ios_base::sync_with_stdio(0);
	cin.tie(0);

    cin >> N >> M;

    //배열 입력 받기
    for(int i=0;i<N;i++)
        cin >> arr[i];
    
    //배열을 누적합로 변경
    for(int i=1;i<=N;i++)
        arr[i]+=arr[i-1];

    //구간 입력 받고 누적 합 출력
    for(int i=0;i<M;i++) {
        int x, y;
        cin >> x>> y;

        cout << arr[y-1]-arr[x-2] << "\n";
    }
}

---

⊙ 결과

 

---

⊙ 마무리

 

 

NONE

 

하트 누르면 위 내용 전부 기억함