[백준 1806] 부분합 : 투포인터 (python / 파이썬)

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

풀이 아이디어)
① 투 포인터 인데, 어차피 모두 자연수이고 부분합은 계속 커지기 때문에 미리 정렬하지 않아도 된다.
② 만약 start = 0 부터 end = N-1 까지 모두 더했는데도 S를 넘지 못하면, while 문에 break를 걸고 0을 출력한다.
③ subsum이 S를 넘었을 경우 result에 수열 길이의 최솟값을 저장한다. 이 때 result는 N이 100,000 이하 여서 초깃값을 1000000으로 저장하였다.
④ start 포인터를 옮기기 전에 A[start]를 빼준다.

N, S = map(int, input().split()) # N : 수열 길이, S : 부분합
A = list(map(int, input().split()))

subsum = 0
end = 0
result = 10000000 # 부분 수열 길이

# start를 차례대로 증가시키며 반복
for start in range(N):
    
    # end를 가능한 만큼 이동
    while (subsum < S and end < N):
        subsum += A[end]
        end += 1
    
        if subsum < S and start == 0 and end == N:
            result = 0
            break
    
    if subsum >= S:
        result = min(result, end-start)
        
    subsum -= A[start]
    
print(result)