문제
https://www.acmicpc.net/problem/14246
풀이
투 포인터를 적용해서 풀었다.
left와 right 모두 0에서 시작해 특정 조건을 만족하면 인덱스를 하나씩 늘려갔다.
이때 주어진 값들은 모두 자연수이므로, 만약 left ~ right의 구간합이 k보다 크다면 right 이후의 모든 구간 또한 k보다 큰 구간합을 갖는다.
- ex. [1 2 3 1] 에서 4 이상의 구간합을 찾는 경우, [1 2 3]의 합이 4보다 크므로 [1 2 3 1]의 구간합 또한 4보다 크게 된다.
n = int(input())
nums = list(map(int, input().split()))
k = int(input())
left, right = 0, 0
sum = 0
count = 0
while (left <= right) :
if sum > k : # 구간합이 k보다 큰 경우
count += (n - right + 1) # 그 이후의 구간들의 구간합도 k보다 클 것이므로 count에 추가
sum -= nums[left] # 이제 구간합을 줄여줘야 하므로, 왼쪽 인덱스 하나 이동
left += 1
elif right == n : # 오른쪽 인덱스가 끝에 도달한 경우
break
else : # 구간합이 k 이하인 경우
sum += nums[right] # 구간합을 늘려줘야 하므로, 오른쪽 인덱스 하나 이동
right += 1
print(count)
728x90