[알고리즘] 백준 21318 - 피아노 체조

1. 문제

피아노를 사랑하는 시은이는 매일 아침 피아노 체조를 한다. 시은이는 N개의 악보를 가지고 있으며, 1번부터 N번까지의 번호로 부른다. 각 악보는 1 이상 109 이하의 정수로 표현되는 난이도를 가지고 있다. 난이도를 나타내는 수가 클수록 어려운 악보이다. 1 ≤ x ≤ y ≤ N 을 만족하는 두 정수 x, y를 골라 x번부터 y번까지의 악보를 번호 순서대로 연주하는 것이 피아노 체조이다.

시은이는 피아노 체조를 할 때, 지금 연주하는 악보가 바로 다음에 연주할 악보보다 어렵다면 실수를 한다. 다시 말하자면, i(x ≤ i < y)번 악보의 난이도가 i + 1번 악보의 난이도보다 높다면 실수를 한다. 특히, 마지막으로 연주하는 y번 악보에선 절대 실수하지 않는다. 시은이는 오늘도 피아노 체조를 하기 위해 두 정수 x와 y를 골랐고, 문득 궁금한 것이 생겼다. 오늘 할 피아노 체조에서 실수하는 곡은 몇 개나 될까?

2. 입력

첫 번째 줄에 악보의 개수 N(1 ≤ N ≤ 100,000)이 주어진다.
두 번째 줄에 1번 악보부터 N번 악보까지의 난이도가 공백을 구분으로 주어진다.
세 번째 줄에 질문의 개수 Q(1 ≤ Q ≤ 100,000)이 주어진다.
다음 Q개의 줄에 각 줄마다 두 개의 정수 x, y(1 ≤ x ≤ y ≤ N)가 주어진다.

3. 풀이

1) 완전탐색 - 시간초과

악보를 비교해가면서 실수를 완전탐색으로 찾는다.
-> 시간 초과 발생

2) 누적합

1번 악보부터 N번 악보까지 각 악보까지 도달했을 때 발생할 수 있는 실수 갯수를 저장한다.
x~y 사이의 실수 갯수는 mistake[y]-mistake[x]가 된다.

4. 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class piano_21318 {

    static int[] arr;
    static int[] mis;

    public static void solution() throws IOException{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
        int n = Integer.parseInt(bf.readLine());
        int q;

        arr = new int[n];
        mis = new int[n];

        StringTokenizer st = new StringTokenizer(bf.readLine());
        for(int i=0;i<n;i++){
            arr[i] = Integer.parseInt(st.nextToken());
        }

        int mistake = 0;
        for(int i=0;i<n-1;i++){
            if(arr[i]>arr[i+1]) {
                mistake++;
            }
            mis[i+1] = mistake;
        }



        q = Integer.parseInt(bf.readLine());
        for(int i=0;i<q;i++){
            st = new StringTokenizer(bf.readLine());
            int x = Integer.parseInt(st.nextToken()) -1;
            int y = Integer.parseInt(st.nextToken()) -1;

            System.out.println(mis[y]-mis[x]);
        }

    }
/*
    public static int check(int x, int y){
        int mistake = 0;
        for(int i = x; i<y; i++){
            if(arr[i]>arr[i+1]){
                mistake++;
            }
        }
        return mistake;
    }
*/
}