[BOJ_21318] 피아노 체조

설명

---

최대 N,Q가 100000인 건으로 일일이 다 체크하면 무조건 시간 초과가 나는 문제였습니다. 따라서, 누적합을 활용하여 문제를 풀었습니다. for N문으로 한 번에 누적된 케이스들의 값을 계속 끌고 가면서 그 사이에 위치한 사이 값이면 해당 누적합의 차이 만큼 빼서 사이에 얼마나 다음 케이스가 큰 케이스인지 체크해 푼 문제 입니다.

 

코드

---

package BOJ.prefix_sum;

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class BOJ_21318 {
    public static void main(String[] args) throws Exception{
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        int N = Integer.parseInt(in.readLine());

        List<Integer> melody = new ArrayList<Integer>();
        StringTokenizer tk = new StringTokenizer(in.readLine()," ");

        for (int i = 0; i < N; i++){
            melody.add(Integer.parseInt(tk.nextToken()));
        }

        int Q = Integer.parseInt(in.readLine());

        int[] sum = new int[N];

        StringBuilder sb = new StringBuilder();

        for (int i = 0; i < N - 1; i++){
            if(melody.get(i) > melody.get(i + 1)){
                sum[i + 1] = sum[i] + 1;
            }else{
                sum[i + 1] = sum[i];
            }
        }

        while (Q-- > 0) {
            tk = new StringTokenizer(in.readLine(), " ");

            int x = Integer.parseInt(tk.nextToken()) - 1;
            int y = Integer.parseInt(tk.nextToken()) - 1;
            sb.append(sum[y] - sum[x] + "\n");
        }
        bw.write(sb.toString());
        bw.flush();
        bw.close();
    }
}

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