[백준] 14246번 K보다 큰 구간 파이썬

문제

n개의 자연수로 이루어진 수열이 주어질 때, 특정 구간 i,j의 합이 k보다 큰 모든 쌍 i,j의 개수를 출력하시오.

입력

첫째 줄에는 숫자들의 개수 n이 주어진다(1≤n≤100,000)

다음 줄에는 숫자 n개가 주어진다. 숫자들은 100,000보다 크지 않은 자연수임이 보장된다.

그 다음 줄에는 숫자 k가 주어진다. (1≤k≤1,000,000,000)

출력

특정 구간 [i,j]의 합이 k보다 큰 모든 쌍 i,j의 개수를 출력하시오.

예제 입력 1

5
1 2 3 2 1
7

예제 출력 1

3

예제 입력 2

5
1 1 1 1 1
2

예제 출력 2

6

제출 답안

• 조합과 같이 모든 경우를 구해서 sum하면 시간 초과가 발생한다.
• https://velog.io/@lse2625/%EB%B0%B1%EC%A4%80-14246%EB%B2%88-K%EB%B3%B4%EB%8B%A4-%ED%81%B0-%EA%B5%AC%EA%B0%84
• 위의 글과 같이 미리 구하고 그 값을 비교해야 시간 초과가 발생하지 않는다.

'''
1. 아이디어
- 0 ~ n까지 합을 com에 저장한다.
- com에 있는 값중 뒤에서부터  num에 저장된 앞의 값을 빼면 해당 구간의 값이된다.
- 그 값을 비교한다.
2. 시간 복잡도
- 
3. 변수
- num []
'''

import sys
input = sys.stdin.readline


n = int(input())
num = list(map(int, input().split()))
k = int(input())
com = []
temp = 0
for i in num:
    temp += i
    com.append(temp)

result = 0
for i in range(n-1, -1, -1):
    j = 0
    if com[i] > k:
        result += 1
    while com[i] - com[j] > k:
        result +=1
        j += 1
print(result)