https://www.acmicpc.net/problem/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])
'Koala - 10기 > 코딩테스트 준비 스터디' 카테고리의 다른 글
[Python/백준] 2346 : 풍선 터트리기 (0) | 2023.05.04 |
---|---|
[백준/Python] 9205번 맥주마시면서 걸어가기 (0) | 2023.05.03 |
[백준/Python] 11659번: 구간 합 구하기 4 (누적합) (0) | 2023.04.03 |
[백준/Python] 17951 흩날리는 시험지 속에서 내 평점이 느껴진거야 (0) | 2023.04.02 |
[백준/Python] 1184 귀농 (0) | 2023.04.02 |