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

#문제

11659번: 구간 합 구하기 4

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

11659번: 구간 합 구하기 4

 

---

#접근방법

슬라이딩 윈도우 기법으로 접근하였다.

반응형

---

#풀이

#include <stdio.h>

int arr[100005];

int main(){
    int n,m;
    int a,b;

    scanf("%d %d",&n,&m);

    for(int i=1;i<=n;i++){
        scanf("%d",&arr[i]);
        arr[i] += arr[i-1];
    }

    for(int i=0;i<m;i++){
        scanf("%d %d",&a,&b);

        printf("%d\n",arr[b]-arr[a-1]);
    }

    return 0;
}

 

구간 합을 구할 때 슬라이딩 윈도우 알고리즘을 사용하였다.

 

슬라이딩 윈도우 알고리즘을 사용하면 배열에 누적합을 저장하고 구간이 들어올 때, 예를들어 3 5 가 들어온다면 arr[5] - arr[2]를 출력하면 구간합을 구할 수 있다.

 

먼저 n,m을 입력받고 n개의 수를 입력받는다. 입력받으면서 이전배열을 계속 더해주어 누적합을 시켜준다.

 

그리고 m개의 구간을 입력받으면서 arr[b] - arr[a-1]을 출력하면 a부터 b까지의 누적합을 O(1)의 시간으로 구할 수 있다.

---

#성능

---

#정리

윈도우 슬라이딩 알고리즘을 알고 있으면 쉽게 풀 수 있는 문제였다.