BOJ_1806(부분합)

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

접근 방식

1. 먼저 10 <= n < 100,000의 범위를 고려했을 때, 투포인터, 이분탐색, 스택, DP 등을 생각해 볼 수 있다. (O(N) = N * N 이상 시간초과)
2. 문제의 규칙이 연속된 수이기 때문에 투포인터를 적용할 수 있다.

구현

알고리즘 요약:
구간 합이 S보다 작을 경우 구간을 오른쪽으로 늘린다 →
구간 합이 S보다 클 경우 구간을 왼쪽부터 줄인다

주의:
값 하나로 조건을 만족할 수 있기 때문에, left 값에 따라 반복문을 종료한다.

import sys
input = sys.stdin.readline

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

# 구간 찾기
left, right = 0, 0
ans = 100_001
current = arr[0]
# right가 아닌 left + 1 < N
# 값 하나만으로도 조건을 만족할 수 있기 때문에
while left + 1 < N:
    # 값 업데이트
    if current >= S:
        ans = min(ans, right - left + 1)
    # 구간 변경
    if right + 1 == N or current >= S:
        current -= arr[left]
        left += 1
    elif left == right or current < S:
        right += 1
        current += arr[right]

if current >= S:
    ans = min(ans, right - left + 1)

if ans == 100_001:
    print(0)
else:
    print(ans)