[백준 시리즈] 21318번 : 피아노 체조 - 실버 1 / Python

---

21318번 : 피아노 체조

출처 : 백준 /  21318번: 피아노 체조 (acmicpc.net)

사용 알고리즘 : 누적 합

 

문제 설명

1. Q번의 쿼리에 대해 x번부터 y번까지 악보를 연주할 때 실수하는 곡이 몇 곡인지 찾아라.

2. 각 악보마다 난이도가 주어지며 숫자가 높을수록 높은 난이도이다.

3. 현재 연주하는 악보가 다음에 연주할 악보보다 어려우면 실수하며, 마지막 곡은 무조건 실수하지 않는다.

 

제한

시간 제한 : 0.5초 / 메모리 제한 : 1024MB

N(1 ≤ N ≤ 100,000)

Q(1 ≤ Q ≤ 100,000)

x, y(1 ≤ x ≤ y ≤ N)

 

문제 풀이

1단계 : 최대 시간복잡도는 얼마인가?

O(QlogN)

 

2단계 : naive하게 해결해보자

x번부터 y번까지 실수의 총합을 구하는 문제이므로 누적 합을 생각할 수 있다. 실수하는 악보의 개수에 대해 누적 합 배열은 다음의 공식을 통해 만들 수 있다.

 

 

또한, 마지막 악보는 무조건 실수하지 않기 때문에 x부터 y-1까지의 누적 합을 찾는다.

 

정답 코드

n = int(input())
arr = list(map(int, input().split()))
ps = [0 for _ in range(n+1)]

for i in range(1, n):
    ps[i] = ps[i-1] + (arr[i-1]>arr[i])
ps[n] = ps[n-1]

q = int(input())
for _ in range(q):
    x, y = map(int, input().split())
    print("%d\n"%(ps[y-1]-ps[x-1]))

 

---