개요

백준 17203번: ∑|ΔEasyMAX|

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

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

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

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

접근 방식

1. 백준11441(합구하기)
   이런 문제들처럼 입력값의 최대치가 크지 않으므로
   합배열을 따로 만들지 않아도 된다.

2. 합배열을 만들어서 풀때는 i-1까지의 차이를 더한 합배열 differSum[i]을 구현하여 풀었다.

	//i번째까지의 구간합의 총합 구현하는 부분 
	differSum[i + 1] =differSum[i]+ abs(inputArr[i] - inputArr[i - 1]);
        
    //인덱스는 1부터 들어오므로 tmp1-1 부터 tmp2-1까지의 합 출력 부분
	cout << differSum[tmp2] - differSum[tmp1] << '\n';

3. 각 시작점에 입력될때마다 그사이 차이를 바로 계산해서 답을 출력하는
   방식이다.

	for (int i = 0; i < Q; i++) {
		int Sum = 0;
		cin >> tmp1 >> tmp2;
		//tmp-1과 tmp1까지의 합부터 tmp2-2부터 tmp2-1까지 더해서 출력
		for (int j = tmp1 - 1; j < tmp2-1; j++) {
			Sum += abs(inputArr[j + 1] - inputArr[j]);
		}
		cout << Sum<<'\n';
	}

하지만 이 방식은 Q와 N의 범위가 커지면 시간초과가 난다.

합배열 사용한 코드

#include<iostream>

using namespace std;

int N = 0, Q = 0;
int inputArr[1001];
int differSum[1001];

//합 배열선언해서 빠르게 처리하도록
void Input() {
	int tmp1 = 0, tmp2 = 0;
	cin >> N >> Q;
	cin >> inputArr[0];
	for (int i = 1; i < N; i++) {
		cin >> inputArr[i];
		//i번째까지의 구간합의 총합
		differSum[i + 1] =differSum[i]+ abs(inputArr[i] - inputArr[i - 1]);
	}
	for (int i = 0; i < Q; i++) {
		cin >> tmp1 >> tmp2;
		//인덱스는 1부터 들어오므로 tmp1-1 부터 tmp2-1까지의 합 출력
		cout << differSum[tmp2] - differSum[tmp1] << '\n';
	}
}

int main() {
	Input();

}

입력값 받을때마다 바로 계산하는 코드

#include<iostream>

using namespace std;

int N = 0, Q = 0;
int inputArr[1001];

//하나하나 다구현해도 어차피 총 연산 100만이라 가능
void Input1() {
	int tmp1 = 0, tmp2 = 0;
	cin >> N >> Q;
	for (int i = 0; i < N; i++) {
		cin >> inputArr[i];
	}
	for (int i = 0; i < Q; i++) {
		int Sum = 0;
		cin >> tmp1 >> tmp2;
		//tmp-1과 tmp1까지의 합부터 tmp2-2부터 tmp2-1까지 더해서 출력
		for (int j = tmp1 - 1; j < tmp2-1; j++) {
			Sum += abs(inputArr[j + 1] - inputArr[j]);
		}
		cout << Sum<<'\n';
	}
}

int main() {
	//이 문제조건은 최대치가 작아서 Input1이나 Input이나 다 답이 나옴
	//Input();
	Input1();
}

문풀후생

배열의 인덱스를 0부터 증가시키는데 반해 문제는 1부터줘서 헷갈리는 부분이있다.
담부턴 배열도 1부터 사용하는 부분도 고려해봐야겠다.