[백준] 부분합

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

1806번: 부분합

 

받은 배열을 순서대로 이동하면서 합을 구한 뒤 그 합이 S 를 넘으면 k = 0 을 시작으로 1씩 더해주면서 temp 가 S 보다 작아질 때까지 array[k] 를 빼준다. 이때 연속된 수들의 부분합이 S 를 넘어가는 길이는 i - k + 2 이며 그 중 최솟값을 반환하면 된다.

 

import sys

N, S = map(int, sys.stdin.readline().split())
array = list(map(int, sys.stdin.readline().split()))
temp = 0
k = 0
answer = N + 1

for i in range(N):
    temp += array[i]
    
    if temp >= S:
        while temp >= S:
            temp -= array[k]
            k += 1
            
        answer = min(answer, i - k + 2)
    
if answer > N:
    print(0)
else:
    print(answer)