[ BOJ ][JAVA][21318] 피아노 체조

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

21318번: 피아노 체조

시간 제한	메모리 제한	제출	정답	맞은 사람	정답 비율
0.5 초	1024 MB	215	100	77	46.951%

문제

피아노를 사랑하는 시은이는 매일 아침 피아노 체조를 한다. 시은이는 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

코드

/*
    정답이 안나와서 좀 해맸었는데, prefixSum()에서 정답을 리턴하는 곳에서
    return dp[r] - dp[l - 1] 이 아니라 dp[r] - dp[l] 이었다.
    이유는 문제를 고려하여 더 고민해보자.
*/
import java.io.*;
import java.util.*;
public class p21318 {
    static int n, q;
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        n = Integer.parseInt(br.readLine());
        int[] arr = new int[n + 1];
        int[] dp = new int[n + 1];
        StringTokenizer st = new StringTokenizer(br.readLine());
        for (int i = 1; i <= n; i++) {
            arr[i] = Integer.parseInt(st.nextToken());
        }

        for (int i = 1; i <= n; i++) {
            dp[i] = dp[i - 1];
            if (arr[i] < arr[i - 1]) {
                dp[i]++;
            }
            //System.out.println("i:"+i+", dp[i]:"+dp[i]);
        }

        StringBuilder sb = new StringBuilder();
        q = Integer.parseInt(br.readLine());
        while (q-- > 0) {
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            int result = prefixSum(x, y, dp);
            sb.append(result).append("\n");
        }
        bw.write(sb.toString());
        bw.flush();
        bw.close();
        br.close();
    }
    static int prefixSum(int l, int r, int[] dp) {
        return dp[r] - dp[l];
    }

}