백준 21318 피아노 체조 Kotlin (누적 합)

문제 출처 : https://www.acmicpc.net/problem/21318

21318번: 피아노 체조

문제

피아노를 사랑하는 시은이는 매일 아침 피아노 체조를 한다. 시은이는 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 이상의 정수 하나로 출력한다. 각 출력은 개행으로 구분한다.

알고리즘 분류

• 누적 합

풀이

주어진 악보들의 난이도를 이용해서 여러 답을 도출해야 한다.

즉, Q이 주어질 때마다, 주어진 구간에서 실수하는 곡의 수를 찾는 것이 아니라,

미리 실수하는 곡들에 대한 누적 결과를 저장해놓고, Q가 주어질 때마다, 이를 재활용하는 것이 핵심이다.

1 2 3 3 4 1 10 8 1

의 예시로 설명하면,

4에서 1 악보를 칠 때는 실수한다.

10에서 8 악보를 칠 때도 실수한다.

8에서 1 악보를 칠 때도 실수한다.

이를 배열로 나타내면

1	2	3	3	4	1	10	8	1
0	0	0	0	1	1	2	3	3

첫 번째 악보부터 다섯 번째 악보까지 연주한다면 1번의 실수가 있고,

첫 번째 악보부터 여섯 번째 악보까지 연주한다면 여전히 1번의 실수가 있다.

만약 여섯 번째 악보부터 여덟 번째 악보까지 연주한다면, 

1 10 8 의 악보를 연주하게 되는데,

1에선 실수가 일어나지 않고,

10과 8에선 실수가 일어나, 총 2번의 실수가 일어난다.

이는, 여덟 번째 악보까지 연주했을 때의 실수 누적에서 여섯 번째 악보까지 연주했을 때의 실수 누적을 빼면 된다.

 

코드

fun main() = with(System.out.bufferedWriter()){
    val br = System.`in`.bufferedReader()
    val n = br.readLine().split(' ').map{it.toInt()}
    val arr = br.readLine().split(' ').map{it.toInt()}
    val q =br.readLine().toInt()
    val result = IntArray(arr.size+1)
    for(i in 1 until result.size){
        if(i==result.size-1){
            result[i]=result[i-1]
        }
        else{
            result[i]=result[i-1]
            if(arr[i-1]>arr[i]){
                result[i]++
            }
        }
    }

    for(i in 0 until q){
        val (from, to) = br.readLine().split(' ').map{it.toInt()}
        write("${result[to-1]-result[from-1]}\n")
    }
    close()
}