[백준] 21318 피아노체조 Python

시간제한이 0.5 인 문제 - 그래서 삽질을 좀 해야 했다..

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

21318번: 피아노 체조

x 부터 y까지 입력값을 받을 때마다 선형탐색으로 실수를 찾아내게 되면 시간초과가 뜰 것 같아서 DP 누적합으로 풀었다. 

누적합 힌트를 보고 풀었고 풀이도 맞는데 시간초과가 나서 세세한 부분을 신경써주어야 하는 문제였다. 

그런데 처음에는 dp를 n+1 길이로 해서 인덱스 값 헷갈리지 않게 하려고 했으나.. n+1 으로 하니 또 시간초과가 난다. 

그리고 sys 라이브러리 사용하지 않고, input()으로 받으니깐 시간초과 난다. 

# 21318
import sys
n = int(sys.stdin.readline())
note = list(map(int, sys.stdin.readline().split())) # 난이도
dp = [0]*n # 누적합 저장 dp
for i in range(1, n):
    if note[i] < note[i-1]:
        dp[i] = dp[i-1] + 1
    else:
        dp[i] = dp[i-1]

q = int(sys.stdin.readline()) # 질문의 개수
for _ in range(q):
    x, y = map(int, sys.stdin.readline().split())
    print(dp[y-1] - dp[x-1])