백준 21318 (피아노 체조) c++

문제

21318번: 피아노 체조

피아노 악보 n개가 주어지고 각 n개의 악보마다 난이도가 주어집니다.

만약 i번째 악보가 i+1악보의 난이도보다 높다면 실수 합니다.

구간 x~y가 주어진다면 실수하는 횟수를 구하는 문제입니다.

 

prefix sum을 이용하여 해결하였습니다.

psum[i] = 1부터 i번째 까지 실수하는 횟수로 정의하였습니다.

구간 [x, y] = psum[y] - psum[x]로 구할 수 있습니다.

---

전체 코드입니다.

#include<iostream>
#include<algorithm>
#include<climits>
#include<string>
#include<vector>
#include<queue>
#include<stack>
#include<deque>
#include<cmath>
#include<time.h>
#include<cstring>
#include<cmath>
#include<cstring>
#include<limits>
using namespace std;
using ll = long long;
using ull = unsigned long long;
ll arr[100001];
ll psum[100001];
int main() {
    ios_base::sync_with_stdio(false), cin.tie(NULL), cout.tie(NULL);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++)
        cin >> arr[i];
 
    psum[1] = 0;
    for (int i = 2; i <= n; i++) {
        if (arr[i] < arr[i - 1])
            psum[i] = psum[i - 1] + 1;
        else psum[i] = psum[i-1];
    }
 
    int q;
    cin >> q;
    for (int i = 0; i < q; i++) {
        int x, y;
        cin >> x >> y;
        cout << psum[y] - psum[x] << '\n';
    }
 
    return 0;
}