[백준] 1806 - 부분합

1. 문제

1806번: 부분합

2. 개요

수열이 주어졌을 때, 그 수열의 연속 부분수열 중 그 합이 S이상인 부분수열 중 가장 짧은 부분수열의 길이를 구하는 문제.

3. 코드 및 추가내용

import sys

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

sums = [0 for _ in range(N+1)]

l, r = 0, N+2
for i in range(1, N+1):
    sums[i] = nums[i-1] + sums[i-1]
    if r > i and sums[i] >= S:
        r = i

ans = r - l

while r < N+1:
    while l < r:
        if sums[r] - sums[l] >= S:
            if r - l < ans:
                ans = r - l
        else:
            break
        l += 1
    r += 1
            
print(0) if ans > N else print(ans)

l, r을 각각 0과 N+2로 초기설정해준다.

누적합을 리스트를 만들어가며 누적합이 S이상이 되는 첫 인덱스를 r로 갱신한다.

이때 누적합이 S이상인 경우가 없어서 r이 N+2로 빠져나왔다면 하단의 while문이 작동하지 않고 자동으로 0을 출력한다.

r이 잘 갱신되었다면 일단 ans의 초기값을 r-l로 잡는다.

이후로 sums[r] - sums[l]이 S이상이 되지 않을 때까지 l을 한 칸씩 이동시키고 l을 이동시킬 수 없다면 r을 한 칸씩 이동시킨다. 이를 반복해나가며 r - l 이 ans보다 작다면 ans를 갱신시킨다.

while문을 빠져나와 답을 출력한다.