[파이썬][백준21318] 피아노 체조

문제링크

21318번: 피아노 체조

 

문제

 

문제풀이

 x, y의 구간에서 주어진 난이도(arr) arr[i] > arr[i+1] 개수를 찾는 문제.
모든 주어진 질문을 완전 탐색으로 하면 시간초과가 났습니다. 구간을 검색해봤던 곳을 또 검색하는 경우가 있을 거라고 생각해서 누적합을 이용하면 된다고 생각했다. 난이도 배열을 한번 돌면서 전 난이도랑 비교하고 누적합을 더해주었다

 따라서, dp[y] - dp[x]가 정답이 된다.

 

파이썬 코드

import sys

"""
피아노 체조
https://www.acmicpc.net/problem/21318
"""
input = sys.stdin.readline

N = int(input())

arr = list(map(int, input().split()))
arr.insert(0, 0)
Q = int(input())
dp = [0] * (N + 1)
answer = ""
for i in range(1, N + 1):
    dp[i] = dp[i - 1]
    if arr[i] < arr[i - 1]:
        dp[i] += 1

for _ in range(Q):
    x, y = map(int, input().split())
    answer += str(dp[y] - dp[x]) + "\n"

print(answer)