[Silver II] K보다 큰 구간 - 14246

문제 링크

성능 요약

메모리: 123464 KB, 시간: 2812 ms

분류

두 포인터

제출 일자

2026년 04월 25일 22:04:59

문제 설명

$n$개의 자연수로 이루어진 수열이 주어질 때, 특정 구간 $[i,j]$ ($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)$의 개수를 출력하시오.

---

💡 해결 방법

💻 코드

import sys
input = sys.stdin.readline
 
n = int(input())
 
l = list(map(int, input().split()))
 
k = int(input())
 
c = 0
 
#누적합
l2 = [0]
 
for i in range(len(l)):
    l2.append(l2[-1] + l[i])
 
 
for s in range(len(l)):
    for e in range(s, len(l)):
        if l2[e + 1] - l2[s] > k:
                c += len(l) - e
                break
            
                
print(c)