[백준/Python] #1806 부분합

문제

 

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

1806번: 부분합

---

Algorithm

sum함수를 사용하면 시간이 초과되므로 투포인터 알고리즘으로 처리하되 부분합을 구할 때 누적합에서 누적합을 빼는 방식으로 진행한다. 부분합이 M 이상이 될 때 그 길이의 최솟값을 구한다.

 

---

 

 

Code

import sys

input = sys.stdin.readline

N, M = map(int, input().split())
array = list(map(int, input().split()))
s = 0
ps = 0

ans = N + 1
i, j = 0, 0
s += array[j]
while j < N:
    if s - ps < M:
        j += 1
        if j < N:
            s += array[j]
    else:
        if i == j:
            ans = 1
            print(ans)
            exit()
        if j - i + 1 <= ans:
            ans = j - i + 1
        ps += array[i]
        i += 1

if ans == N + 1:
    ans = 0
print(ans)