부분합 - 백준 #1806, 누적합/두 포인터

문제

10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N (10 ≤ N < 100,000)과 S (0 < S ≤ 100,000,000)가 주어진다. 둘째 줄에는 수열이 주어진다. 수열의 각 원소는 공백으로 구분되어져 있으며, 10,000이하의 자연수이다.

출력

첫째 줄에 구하고자 하는 최소의 길이를 출력한다. 만일 그러한 합을 만드는 것이 불가능하다면 0을 출력하면 된다.

예제 입력 1

10 15
5 1 3 5 10 7 4 9 2 8

예제 출력 1

2

풀이

import sys
N , S = map(int , sys.stdin.readline().split())
a = list(map(int , sys.stdin.readline().split()))

i,j,hap,r = 0,0,0,float('inf')	앞 포인터, 뒤 포인터, 부분합, 길이
# 부분합이 S 이상 될 때까지 뒤 포인터 전진, 거기서 다시 부분합이 S 이상 되는동안 앞 포인터 전진
# 부분합이 S보다 작아지면 다시 뒤 포인터 전진, 찾은 길이 중 최소값 출력
while(True):
    if hap >= S and r > j-i:
        r = j-i
    if hap >= S:
        hap -= a[i]
        i += 1	# 앞 포인터 한 칸 이동
    elif j == N:	# 뒤 포인터가 끝에 도달하면 멈춤
        break
    else:
        hap += a[j]
        j += 1	# 뒤 포인터 한 칸 이동
print(r if r!=float('inf') else 0)