해당 문제는 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 것이 목표임.
이때, start 포인터와 end 포인터를 사용하여 특정 조건까지 end 포인터를 이동시키면서 부분합을 계산하고, 그 합이 S 이상이 되는 순간 start 포인터를 이동시켜 최소 길이를 구하는 것임.
길이가 0이 될수도 있나?
for문에서 start를 1씩 증가시키면서 end를 이동시켜 나가다보면 자연스럽게 처리되므로 별도의 처리를 하지 않아도 됨.
코드
"""
1. 아이디어
- for문을 통해서 투 포인터로 문제 접근
2. 시간복잡도
- 투 포인터 O(N) : 1e^5 < 2억개 가능!
3. 자료구조
- 수열 저장 list[]
- 부분합 저장 int
- 길이 저장 int
"""
import sys
input = sys.stdin.readline
N,S = map(int, input().split())
A = list(map(int, input().split()))
sum = 0
minLength = float('inf')
end = 0
def solve():
global sum, minLength, end
for start in range(N):
# 특정 조건까지 end 포인터 이동
while sum < S and end < N:
sum += A[end]
end += 1
# while문을 빠져나와서, 문제의 합과 같은지 확인
if sum >= S:
minLength = min(minLength, end - start)
# 초기화
sum -= A[start]
solve()
if minLength == float('inf'):
print( 0 )
else:
print( minLength )
