(C++) - 백준(BOJ) 21318번 : 피아노 체조

www.acmicpc.net/problem/21318

21318번: 피아노 체조

부분합 문제였습니다.

 

풀이방법

 1. 악보 1부터 실수를 할 때마다 배열 d의 i+1번에 실수횟수를 1더해서 저장해줍니다.

 2. d[end] - d[start]시 해당 구간 사이의 실수횟수를 구할 수 있습니다.

 

Code

#include <bits/stdc++.h>
#define fastio ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
using namespace std;

int n, t, piv, score[100001], d[100001];

int main(){
    fastio;
    cin >> n;
    for(int i = 1; i <= n; i++) cin >> score[i];
    for(int i = 1; i <= n; i++){
        if(score[i] > score[i+1]) piv++;
        d[i+1] = piv;
    }
    cin >> t;
    while(t--){
        int start,end;
        cin >> start >> end;
        cout << d[end] - d[start] <<'\n';
    }
}