BaekJoon 1806번 : 부분합 (python)

BaekJoon 1806번 : 부분합 (G4 25.894%)

해당 문제는 주어진 길이 N짜리 수열에서 연속된 수들의 부분합 중에 그 합이 S이상이 되는 것중 가장 짧은 것의 길이를 구하는 문제이다.

해당 문제는 주어진 수열을 그대로 사용해야하는 문제이기 때문에 정렬하지 않은 상태에서 문제를 풀어야 한다.
s = start, e = end

• 이 문제는 구간합, 부분합을 구해야 하는 부분이기에 누적합을 이용해서 미리 해당 인덱스까지의 합을 구해 놓는다.
• s와 e를 0과 1 인덱스에서 시작하며 포인터를 증가시킨다.
• 만약 s와 e가 가리키는 해당 부분합이 주어진 S이상일 때 기존의 temp와 e-s를 비교해서 더 짧은 길이로 갱신시켜준다.
  • 이때 start를 증가시켜주어 부분합의 길이가 더 짧아질 수 있기 때문에 start를 1증가 시켜준다.
• 만약 부분합이 S보다 작을 경우 부분합을 키워줘야 하기 때문에 e를 증가 시켜준다.
• while문은 기본적으로 부분합을 구해야하기 때문에 s는 e보다 작아야 하며 e는 누적합 리스트 범위를 넘지 않아야 한다.
• while문이 끝났을 때 길이를 뜻하는 변수 temp가 갱신되지 않았다면 그러한 합을 만드는 것이 불가능하다는 것을 의미하기 때문에 0을 출력하고 갱신되었을 때는 temp를 출력하게 된다.

import sys
input = sys.stdin.readline

N, S = map(int,input().split())
arr = list(map(int,input().split()))

d = [0]*(N+1)
for i in range(1, N+1) :
    d[i] = d[i-1] + arr[i-1]

s = 0
e = 1
temp = 1e10
while s < e and e <= N:
    if d[e] - d[s] >= S :
        temp = min(temp,e-s)
        s+=1
    else :
        e+=1
if temp == 1e10 :
    print(0)
else :
    print(temp)