[C++] 백준 21318번: 피아노 체조

문제 링크

21318번: 피아노 체조

문제 요약

악보의 x번부터 y번까지 연주를 한다. 이때, i번 악보의 난이도가 i + 1번 악보의 난이도보다 높다면 실수를 하게 된다. 연주하는 악보들 중 마지막 악보를 연주할 때는 실수를 하지 않는다. 구간이 주어지면 각 구간을 연주할때 실술를 몇번 하게 되는지 출력해야 한다.

접근 방법

배열을 하나 준비해주고, 실수를 하게 되는 악보의 인덱스에는 1, 그렇지 않는 인덱스에는 0을 저장해줍니다. 그리고 누적합 배열을 미리 처리해줍니다. 이제 구간을 입력 받으면, 구간의 누적합을 출력해주면 됩니다.

y번 악보에서는 절대 실수를 하지 않고, i번 악보의 실수는 i + 1번의 영향을 받게 됩니다. 따라서 매 질의마다 sum[y - 1] - sum[x - 1]을 출력해주었습니다.

코드

#include <bits/stdc++.h>

using namespace std;

const int MAX = 100001;
int arr[MAX], prefix_sum[MAX];

int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	int n;
	cin >> n;

	for (int i = 1; i <= n; i++)
		cin >> arr[i];

	for (int i = 1; i <= n - 1; i++)
		if (arr[i] > arr[i + 1])
			prefix_sum[i] = 1;

	for (int i = 2; i <= n; i++)
		prefix_sum[i] += prefix_sum[i - 1];

	int q;
	cin >> q;

	while (q--) {
		int x, y;
		cin >> x >> y;
		cout << prefix_sum[y - 1] - prefix_sum[x - 1] << '\n';
	}

	return 0;
}