[Python] 백준 #1806 부분합

📚문제: #1806 부분합(Gold 4)

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

입력

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

출력

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

예제

(Input)
10 15
5 1 3 5 10 7 4 9 2 8

(Output)
2

아이디어 및 구현

import sys

# N, S가 주어집니다.
N, S = map(int, sys.stdin.readline().split())

# 수열이 주어집니다.
seq = list(map(int, sys.stdin.readline().split()))

s = 0
e = 0

# 구간 합 변수 초기화
total = seq[s]

# 최소 길이 초기화
length = int(1e9)

# Two Pointers Algorithm
while True:
	
    # S보다 작을 때
    if total < S:

        if e == N-1:

            break

        e += 1
        total += seq[e]
    
    # S보다 크거나 같은 순간
    elif total >= S:
		
        # 최소 길이 갱신
        length = min(length, e-s+1)

        total -= seq[s]
        s += 1    

# 구간 합이 S보다 크거나 같은 경우가 없었을 때 : 최소 길이 갱신 안됨
if length == int(1e9):
    
    print(0)

# 최소 길이 출력
else:
    
    print(length)