백준 1806 부분합

문제

👀 문제 사이트 : https://www.acmicpc.net/problem/1806

풀이

난이도 : Gold IV

이 문제는 수열에서 연속된 부분합에서 정해진 값을 넘어서는 부분합들 중 길이가 최소인 부분합의 길이를 구하는 문제이다.
수열의 길이 n은 100000이하이므로 완전탐색을 하기로 생각하였다.

1) start 포인터와 end 포인터를 만들어 부분합의 시작과 끝을 표시한다. (0, 0으로 초기화)
2) 만약 s보다 값이 작다면 end 포인터만 1씩 증가시킨다.
3) s보다 값이 크다면 조건에 만족하므로 result를 업데이트하고, start 포인터를 1씩 증가시킨다.
4) 반복문을 이용하여 1~5의 방법으로 end포인터가 수열의 끝부분에 도착할 때까지 탐색을 진행한다.

코드

n, s = map(int, input().split())

numbers = list(map(int, input().split()))

start = 0
end = 0

result = int(1e9)
tmp = numbers[end]
while True:
    if tmp >= s:
        result = min(result, end-start+1)
        if start == end:
            break
        tmp = tmp - numbers[start]
        start = start + 1
    else:
        end = end + 1
        if end == n:
            break
        tmp = tmp + numbers[end]
        
        
if result == int(1e9):
    print(0)
else:
    print(result)