백준 21318번 피아노 체조 / C++ / 누적합 (Prefix Sum)

알고리즘 개념 누적합

누적합에 대해 잘 모른다면 이전에 정리해 둔 개념 정리를 한번 읽어보고 오는 것을 추천합니다.

[알고리즘] 누적합 (prefix sum)

[알고리즘] 누적합 (prefix sum)

 

백준 21318번 피아노 체조

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

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 이상의 정수 하나로 출력한다. 각 출력은 개행으로 구분한다.

예제 보려면 더보기 클릭

예제 입력 1

9
1 2 3 3 4 1 10 8 1
5
1 3
2 5
4 7
9 9
5 9

예제 출력 1

0
0 
1 
0 
3

예제 입력 2

6
573 33283 5572 346 906 567
5
5 6
1 3
2 2
1 6
3 6

예제 출력 2

1
1
0
3
2

---

문제 설명

예제 1번을 통해 문제를 살펴보자.

1 2 3 3 4 1 10 8 1

 지금 연주하는 악보가 바로 다음에 연주할 악보보다 어렵다면 실수를 한다.

i번 악보가 i+1보다 난이도가 높다면 실수한다. 전체에서 봤을때 실수하는 부분은 다음과 같이 찾을 수 있다.  1 2 3 3 4 1 10 8 1우리가 필요한 부분은 빨간색 부분이므로 그외의 부분은 0 틀리는 부분은 1로 표시한다. 

0 0 0 0 1 0 1 1 0

이 과정으로 코드로 짜면 다음과 같다. i-1번이 현재 i보다 크다면 1 작다면 0으로 대입한다.

for (int i = 0; i < n; i++) {
		cin >> arr[i];
		if (i != 0) {
			if (arr[i-1] > arr[i])
				arr[i-1] = 1;
			else
				arr[i - 1] =0;
		}
	}

이렇게 하면 정리된 배열을 얻을 수 있다. 그러나 문제에서 원하는 것은 틀린 악보의 개수가 아닌 연주했을때 몇번을 틀리는 것인가? 이다. 

인덱스	0	1	2	3	4	5	6	7	8
arr	0	0	0	0	1	0	1	1	0

1~3번 악보(인덱스 0~2번)를 연주하면 틀리는 악보는 없다. 0개

2~5번 악보(인덱스 1~4번)이라면 틀리는 악보는 5번 1개이다. 

5~9번 악보(인덱스 4~8번)이라면 틀리는 악보는 5번, 7번, 8번 3개이다. 

정리하자면 각 x번에서 y번까지 연주한 악보의 틀리는 갯수는 누적합으로 구할 수 있다. 

위 배열을 누적합으로 나타내면 다음과 같기 때문이다. 

인덱스	0	1	2	3	4	5	6	7	8
arr	0	0	0	0	1	1	2	3	3

1~5번악보라면 틀리는 악보는 5번 1개이다. arr[4]

5~6번 악보여도 틀리는 악보는 5번 1개이다. arr[5]-arr[3]

6~7번 악보라면 틀리는 악보는 7번 1개이다. arr[6]-arr[4]  

정리하면 x~y번 악보에서 틀리는 악보의 개수는

arr[y-1] - arr[x-2]

이다.

 

다만 이렇게만 고려하면 예외 상황이 발생할 수 있기 때문에 틀렸다. 

1. x와 y의 범위가 1부터 시작이므로 x가 1일때 arr[-1]음수 인덱스이므로 오류 발생한다. 

x가 1일때에는 arr[y-1]만 출력하도록 따로 경우를 준다.

2. y가 1일때

난 이거때문에 틀렸었다.. 악보가 x와 y 모두 1일때에는 틀리는 악보는 0개이다.

마지막으로 연주하는 y번 악보에선 절대 실수하지 않는다. -문제 일부

이렇게 예외 사항까지 다 수정했다면 이제 제출하면 된다. 

---

제출한 코드(C++)

#include <iostream>
#include <string>
#include <algorithm>
#include <vector>
using namespace std;
using ll = long long int;
//vector <int> v;
int main(void) {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	ll arr[100005];
	ll n,q, x, y;
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> arr[i];
		if (i != 0) {
			if (arr[i-1] > arr[i])
				arr[i-1] = 1;
			else
				arr[i - 1] =0;
		}
	}
	for (int i = 1; i < n; i++) {
		arr[i] += arr[i - 1];
	}
	
	
	cin >> q;
	ll cnt = 0;
	for (int i = 0; i < q; i++) {
		cnt = 0;
		cin >> x >> y;
		if (x >= 2 && y >= 2)
			cout << arr[y - 2] - arr[x - 2] << "\n";
		else if (y == 1)
			cout << 0 << "\n";
		else
			cout << arr[y - 2] << "\n";
	}
}