[BOJ/Silver 4] 백준 17203 ∑|ΔEasyMAX|(C++)

문제 링크

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

17203번: ∑|ΔEasyMAX|

 

문제

작곡가인 GUN은 박자의 빠르기가 변화하는 곡을 쓰는 걸 좋아한다.

혼신의 힘을 다해 곡을 완성한 GUN은 자기가 쓴 곡의 초당 박자 변화량의 합이 얼마나 되는지 궁금해졌다. 하지만 GUN의 노래는 박자가 변화하는 곳이 많아 구간의 변화량 합을 일일이 계산하기 어렵다. GUN은 당신에게 이 곡의 특정 부분들의 구간별 초당 박자 변화량의 합을 구해달라고 요청했다. GUN을 도와 주어진 구간들의 초당 박자 변화량의 합을 구해주자.

단, i 초와 j 초 구간 사이의 초당 박자 변화량의 합은 ∑k=ij−1|ak+1−ak| 라고 정의하고 j−1<i인 경우엔 ∑k=ij−1|ak+1−ak|=0이다.

그리고 기호 |a|는 임의의 실수 a에 대해 a<0 이면 |a| = -a 이고 a≥0 이면 |a| = a임을 나타내는 기호이다.

입력

입력의 첫 번째 줄에는 GUN이 쓴 노래의 길이 N(1 ≤ N ≤ 1,000) 초와 초당 박자 변화량의 합을 구해야 하는 구간의 수 Q(1 ≤ Q ≤ 1,000)이 공백으로 구분되어 주어진다.

입력의 두 번째 줄에는 순서대로 GUN이 쓴 노래의 박자 빠르기를 나타내는 수열 a1 a2, ... , an 이 공백으로 구분되어 주어지며, ai (-10^4 ≤ ai ≤ 10^4)는 i 초일 때 박자의 빠르기라고 한다.

입력의 세 번째 줄부터 Q 줄에 걸쳐 변화량의 합을 구해야 하는 구간의 시작점과 끝점 Q(i,l), Q(i,r) (1 ≤ Q(i,l) ≤ Q(i,r) ≤ N)가 주어진다.

출력

GUN이 쓴 곡의 구간의 초당 박자 변화량의 합을 입력 순서대로 Q 줄에 걸쳐 출력한다.

예제 입력 1

4 3
100 101 382 573
1 1
1 3
2 4

예제 출력 1

0
282
472

위 예제의 입력에서,

첫 번째 구간 [1, 1]의 구간 변화량의 합은 0이다.

두 번째 구간 [1, 3]의 구간 변화량 합은 |101-100| + |382-101| = 1 + 281 = 282이다.

세 번째 구간 [2, 4]의 구간 변화량 합은 |382-101| + |573-382| = 281 + 191 = 472이다.

예제 입력 2

5 3
1 0 1 0 -11
1 5
3 5
2 4

예제 출력 2

14
12
2

위 예제의 입력에서,

첫 번째 구간 [1, 5]의 구간 변화량의 합은 |0-1| + |1-0| + |0-1| + |(-11)-0| = 1 + 1 + 1 + 11 = 14이다.

두 번째 구간 [3, 5]의 구간 변화량의 합은 |0-1| + |(-11)-0| = 1 + 11 = 12이다.

세 번째 구간 [2, 4]의 구간 변화량의 합은 |1-0| + |0-1| = 1 + 1 = 2이다.

알고리즘 분류

• 누적 합

풀이

i번째 원소와 i-1번째 원소의 차의 절댓값의 누적 합을 구해준다.

Q번 L, R을 입력받고, R-1이 L보다 작다면 0을 출력하고, 그게 아니라면 L부터 R까지의 i번째 원소와 i-1번째 원소의 차의 절댓값의 합을 구해준다.

코드

#include <iostream>
#include <string>
#include <cmath>
#include <unordered_set>
#include <unordered_map>
#include <bitset>
#include <stack>
#include <queue>
#include <vector>
#include <algorithm>
#include <climits>
#define FASTIO cin.tie(NULL); cout.tie(NULL); ios::sync_with_stdio(false);
#define MAX 1001
#define LL long long
#define INF 1e9

using namespace std;
int N, Q;
LL MAP[MAX];
LL Sum[MAX];
LL Answer = 0;

void Input() {
	cin >> N >> Q;
	for (int i = 1; i <= N; i++) {
		cin >> MAP[i];
		Sum[i] = Sum[i - 1] + abs(MAP[i] - MAP[i - 1]);
	}
}

void Find_Answer() {
	while (Q--) {
		int L, R;
		cin >> L >> R;
		if ((R - 1) < L) {
			cout << 0 << "\n";
		}
		else {
			cout << Sum[R] - Sum[L] << "\n";
		}
	};
}

int main() {
	FASTIO
	Input();
	Find_Answer();

	return 0;
}