[백준 1806] 부분합 (python)

풀이

시간제한이 무척 짧으므로 시간 복잡도가 O(N)인 투포인터 알고리즘을 사용하여 풀어야 한다.

 

# 부분 합 

N, S = map(int, input().split(" "))

num = list(map(int,input().split(" ")))
start=0
end = 0

part_sum = num[0]
ans = 100001
cnt = 1
while start < N and end < N:
  if S <= part_sum :
    if ans > cnt :
      ans = cnt
    part_sum -= num[start]
    cnt -= 1 
    start += 1
  else :
    end += 1
    cnt += 1
    if end < N:
      part_sum += num[end]

if ans == 100001:
  print(0)
else :
  print(ans)