21318번: 피아노 체조
피아노를 사랑하는 시은이는 매일 아침 피아노 체조를 한다. 시은이는 N개의 악보를 가지고 있으며, 1번부터 N번까지의 번호로 부른다. 각 악보는 1 이상 109 이하의 정수로 표현되는 난이도를
www.acmicpc.net
문제
피아노를 사랑하는 시은이는 매일 아침 피아노 체조를 한다. 시은이는 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 이상의 정수 하나로 출력한다. 각 출력은 개행으로 구분한다.
코드
import sys
input = sys.stdin.readline
n = int(input())
sheet = [0] + list(map(int, input().split()))
mistake = [0] * (n+1)
for i in range(1, n):
mistake[i] = mistake[i-1] + (1 if sheet[i] > sheet[i+1] else 0)
mistake[n] = mistake[n-1]
for _ in range(int(input())):
x, y = map(int, input().split())
print(mistake[y-1]-mistake[x-1])
주의해야할 점은 mistake 배열에는 i번째 악보가 i+1번째 악보, 즉 다음 악보보다 어렵다면 실수를 한다고 생각해서 1을 더해주는 것이라서 우리가 [x, y] 범위에서 볼 때 마지막인 y는 절대 실수하지 않는다고 했으므로 mitake[y]가 아닌 mistake[y-1]을 봐야한다.
'문제풀이 > 누적합' 카테고리의 다른 글
[Python/파이썬] 백준 2015번 수들의 합 4 (0) | 2023.05.10 |
---|---|
[Python/파이썬] 백준 15724번 주지수 (0) | 2023.04.12 |
[Python/파이썬] 백준 11660번 구간 합 구하기 5 (0) | 2023.03.24 |
[Python/파이썬] 백준 20438번 출석체크 (0) | 2023.03.23 |
[Python/파이썬] 백준 2167번 2차원 배열의 합 (0) | 2023.03.23 |