[백준 21318 c++ V] 피아노 체조

풀이 원본: 

https://github.com/xhaktmchl/Algorithm_study/blob/main/BOJ/%EB%88%84%EC%A0%81%ED%95%A9/%5B%EB%B0%B1%EC%A4%80%2021318%20c%2B%2B%20V%5D%20%ED%94%BC%EC%95%84%EB%85%B8%20%EC%B2%B4%EC%A1%B0.cpp

GitHub - xhaktmchl/Algorithm_study: 알고리즘 이론 및 문제풀이

#include <iostream>
#include <algorithm>
using namespace std;
/*
[백준 21318 c++ V] 피아노 체조
문제:
접근1: 완탐 -> 시간 초과
접근2: 누적합-> 구간 까지의 실수 갯수 저장
시간복잡도: O(n)
풀이:
    //1.입력
    //2.누적합: 실수한 곡의 갯수
    //만약 a[i] > a[i+1] 이라면 실수+1
    //아니라면 그대로
    //3.q번 구간합 구하기
*/
int n,q,s,e;
int a[100010];
int psum[100010];

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

    //1.입력
    cin >> n;
    //2.누적합: 실수한 곡의 갯수
    //만약 a[i] > a[i+1] 이라면 실수+1
    //아니라면 그대로
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
    }

    for (int i = 1; i <= n; i++) {
        
        if (a[i] < a[i - 1]) psum[i] = psum[i - 1] + 1;
        else psum[i] = psum[i - 1];
    }
    //3.q번 구간합 구하기
    cin >> q;
    for (int i = 0; i < q; i++) {
        cin >> s >> e;

        cout << psum[e] - psum[s] << '\n';
    }
    return 0;
}