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

문제

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)