[백준 21318] 피아노 체조 (C++)

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

문제

---

피아노를 사랑하는 시은이는 매일 아침 피아노 체조를 한다. 시은이는 N개의 악보를 가지고 있으며, 1번부터 N번까지의 번호로 부른다. 각 악보는 1 이상 109 이하의 정수로 표현되는 난이도를 가지고 있다. 난이도를 나타내는 수가 클수록 어려운 악보이다. 1 ≤ x ≤ y ≤ N 을 만족하는 두 정수 x, y를 골라 x번부터 y번까지의 악보를 번호 순서대로 연주하는 것이 피아노 체조이다.

시은이는 피아노 체조를 할 때, 지금 연주하는 악보가 바로 다음에 연주할 악보보다 어렵다면 실수를 한다. 다시 말하자면, i(x ≤ i < y)번 악보의 난이도가 i + 1번 악보의 난이도보다 높다면 실수를 한다. 특히, 마지막으로 연주하는 y번 악보에선 절대 실수하지 않는다. 시은이는 오늘도 피아노 체조를 하기 위해 두 정수 x와 y를 골랐고, 문득 궁금한 것이 생겼다. 오늘 할 피아노 체조에서 실수하는 곡은 몇 개나 될까?

 

입력

---

첫 번째 줄에 악보의 개수 N(1 ≤ N ≤ 100,000)이 주어진다.

두 번째 줄에 1번 악보부터 N번 악보까지의 난이도가 공백을 구분으로 주어진다.

세 번째 줄에 질문의 개수 Q(1 ≤ Q ≤ 100,000)이 주어진다.

다음 Q개의 줄에 각 줄마다 두 개의 정수 x, y(1 ≤ x ≤ y ≤ N)가 주어진다.

출력

---

x번부터 y번까지의 악보를 순서대로 연주할 때, 몇 개의 악보에서 실수하게 될지 0 이상의 정수 하나로 출력한다. 각 출력은 개행으로 구분한다.

 

문제 풀이

---

누적합 문제.

 

각 인덱스마다 해당 인덱스까지 몇 번 실수하는지 누적합을 기록하는 배열에 저장해둔다. 이 범위는 처음부터 i번째 인덱스까지의 실수가 기록되어 있으므로, x번 부터 y번까지의 실수 횟수를 구하고 싶다면 y번까지의 횟수를 구한 후 x-1번까지의 실수 횟수를 빼주면 된다.

단, y번째 곡은 실수를 하지 않으므로, 누적합을 구할 때 누적합[y] > 누적합[y+1]라 실수를 한다고 기록되어있다면 구한 수에서 1을 빼주어야 한다.

 

아래는 코드.

#include <iostream>
using namespace std;

int main()
{
	cin.tie(NULL);
	ios::sync_with_stdio(false);

	int N, M, start, end;
	cin >> N;
	int* arr = new int[N];
	int* mistakes = new int[N+1];
	for (int i = 0; i < N; i++)
	{
		cin >> arr[i];
	}
	mistakes[0] = 0;
	for (int i = 1; i < N; i++)
	{
		mistakes[i] = mistakes[i - 1];
		if (arr[i-1] > arr[i])
		{
			mistakes[i]++;
		}
	}
	mistakes[N] = mistakes[N - 1];
	cin >> M;
	for (int i = 0; i < M; i++)
	{
		cin >> start >> end;
		if (end != N && arr[end-1] > arr[end])
		{
			cout << mistakes[end] - mistakes[start - 1] - 1<< "\n";
		}
		else
		{
			cout << mistakes[end] - mistakes[start - 1] << "\n";
		}
	}
	return 0;
}