부분합[백준 1806]

https://www.acmicpc.net/problem/1806

 

배열 첫 번째 숫자부터 계속 오른쪽으로 window를 늘려가지만, 목표 합 s보다 큰 경우는 window 사이즈를 줄이기 위해 앞 부분인 start를 한 칸 이동한다. 

 

def min_subarray_length(n, s, arr):
    start, end = 0, 0
    current_sum = 0
    min_length = float('inf')
    
    while end < n:
        # 윈도우 확장
        current_sum += arr[end]
        end += 1
        
        # 조건 만족 시 윈도우 축소
        while current_sum >= s:
            min_length = min(min_length, end - start)
            current_sum -= arr[start]
            start += 1
    
    return min_length if min_length != float('inf') else 0

# 예제 입력
n,s=map(int,input().split())
arr=list(map(int,input().split()))


# 함수 호출
result = min_subarray_length(n, s, arr)
print(result)  # 출력: 2