[백준/파이썬] #1806

풀이를 참고하지 않고 30분 안에 풀었다!

시간제한이 0.5초였어서 O(N^2)가 아닌 O(N)에 풀어야 했고, 그러려면 투 포인터를 사용해야 했다. 

 

left, right 이라는 두 개의 포인터를 사용했고, 현재 배열의 합이 S 이상이 될 때까지 right 포인터를 1씩 증가시켜 배열에 원소를 추가했다. 

그러다가 합이 S이 넘으면 다시 left 포인터를 1씩 증가시켜서, 배열의 원소를 감소시켰다. 합이 S 이상인 배열의 '최소' 길이를 구해야 하기 때문이다. 

import sys

input = sys.stdin.readline

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

left, right = 0, 1
current_sum, min_length = arr[left], N+1

while right < N:
    while current_sum < S and right < N:
        current_sum += arr[right]
        right += 1
    if current_sum >= S:
        min_length = min(min_length, right - left)
    while current_sum >= S and left < right:
        current_sum -= arr[left]
        left += 1
    if left > 0 and current_sum + arr[left-1] >= S:
        if current_sum >= S:
            min_length = min(min_length, right - left)
        else:
            min_length = min(min_length, right - left + 1)

min_length = 0 if min_length == N+1 else min_length
print(min_length)