백준 17203 번 : ∑|ΔEasyMAX|

문제 링크 : https://www.acmicpc.net/problem/17203

17203번: ∑|ΔEasyMAX|

 

 

 문제 설명 

 

1. N개의 문자와 M개의 구간이 주어진다.

2. M개의 구간이 주어질 때 M 구간의 변화량의 합을 출력.

 

 알고리즘 

 

1. Prefix Sum(구간합 배열) 을 통해 변화량을 구한다.

2. 예제를 살펴보면 

 (1,1) -> 변화량 0 

 (1,3) -> 1+ 282 이다 그러므로 구간합 배열에서  arr[3-1] - arr[1-1] = 282

 (2,4) -> arr[4-1] - arr[2-1] = arr[3] - arr[1] = 472

 

 

 코드 

 

#include<iostream>
#include<math.h>
using namespace std;
 
int main() {
    int n,m;
    int num[1001];
    int arr[1001];
 
    scanf("%d%d", &n,&m);
    
    for (int i = 0; i < n; i++) {
        scanf("%d", &num[i]);
        arr[i] = arr[i-1]+abs(num[i] - num[i - 1]);
        }
    for (int i = 0; i < m; i++) {
        int a, b;
        scanf("%d%d", &a, &b);
        printf("%d\n", arr[b-1] - arr[a - 1]);
    }
 
    
 
}