[누적합 / python] 백준 21318. 피아노 체조

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

21318번: 피아노 체조

 

문제 해석

해당 문제는 구간을 주고, 그 구간 내에서 특정 조건을 만족하는 경우를 '세어' 달라고 했다. 만약 일반적인 경우처럼 크게 입력값을 받는 loop로 묶고, 그 안에서 입력받은 것에 따라 x부터 y까지 슬라이싱을 하고, 슬라이싱한 배열을 sum 함수로 돌린다면 시간복잡도가 O(Q*N*(y-x))이다.

 

최악의 경우 이미 0.5초를 훌쩍 넘겨 버리므로, 다른 방안을 고려해야 한다. 마침 "구간"이라는 힌트와 "세어"달라는 힌트가 존재한다. 누적합을 이용한다면 위 문제를 쉽게 풀 수 있을 것이다.

 

문제 풀이

import sys
input = sys.stdin.readline

t = int(input())
li = list(map(int, input().split()))

res = [0] * t
for i in range(len(li)-1):
    if li[i+1] < li[i]:
        res[i]=1

prefix_sum = [0] * (t+1)
for i in range(1,t+1):
    prefix_sum[i] = prefix_sum[i-1] + res[i-1]

for _ in range(int(input())):
    i, j = map(int, input().split())
    print(prefix_sum[j-1] - prefix_sum[i-1])