[백준 1806] 부분합 (python)

1806번: 부분합

---

투포인터 또는 부분합을 이용하자!

 

부분합

import sys
input = sys.stdin.readline


N, S = map(int, input().split())
arr = [0]
arr.extend(list(map(int, input().split())))

for i in range(1, len(arr)):
    arr[i] += arr[i-1]

result = N+1
left = 0
right = 1
while left <=N and right <= N:
    if arr[right]-arr[left] <S:
        right+=1
    else:
        result = min(result, right-left)
        left+=1
    
if result == N+1:
    print(0)
else:
    print(result)
    

 

투포인터

import sys
input = sys.stdin.readline


N, S = map(int, input().split())
arr = list(map(int, input().split()))

result = N+1
_sum = 0
left = 0
right = 0
while True:
    if _sum >= S:
        result = min(result, right-left)
        _sum -= arr[left]
        left += 1
    elif right == N:
        break
    else:
        _sum += arr[right]
        right += 1

if result == N+1:
    print(0)
else:
    print(result)