[백준] 1806번 - 부분합 (파이썬)

https://www.acmicpc.net/problem/1806

# 부분합
import sys
MAX = sys.maxsize
input = sys.stdin.readline
N, S = map(int, input().split())
arr = list(map(int, input().split()))

end = 0
sum = 0
result = MAX
for start in range(N):
    while end < N and sum < S:
        sum += arr[end]
        end += 1
    if sum >= S:
        result = min(result, end-start)
    sum -= arr[start]

if result == MAX:
    print(0)
else:
    print(result)

 

투포인터

1. start와 end로 연속되는 수열의 합(sum)을 구하고 목표값과 비교

2. 조건을 만족하면 result와 현재 수열의 길이를 비교하여 초기화

3. sum에서 start를 하나씩 빼면서 반복

 

sum < S 이고 end == N 이면 이후의 값은 모두 S보다 작아서 break를 해주면 시간복잡도를 줄일 수 있다.

그러나 시간복잡도가 여유가 있어서 그냥 제출