난이도 : 골드4
유형 : 투포인터
https://www.acmicpc.net/problem/1806

문제 접근

길이 N짜리 수열이 주어진다.
그리고 타겟넘버 S가 주어지는데
이 수열의 부분합 중 크기가 S 이상이 되는 것들 중에 가장 길이가 짧은 부분합의 크기를 출력하는 문제이다.

[5, 1, 3, 5, 10, 7, 4, 9, 2, 8] 가 주어지고 S가 15라면
조건을 만족하는 가장 짧은 부분합의 길이는 5+10의 길이 2이다.

해결 아이디어

투 포인터 기법을 사용해 연속된 구간을 탐색한다.
두 포인터 left, right를 두고:
right를 늘려가며 누적합을 구하고,
누적합이 S 이상이 되면 left를 옮기며 구간을 줄여 최소 길이를 찾는다.

해답 및 풀이

import sys
input = sys.stdin.readline

INF = float('inf')

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

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

left = 0  
right = 0  
total = 0

# 정답으로 출력할 최소 길이. 일단 최대값으로 초기화
min_length = N + 1 

while right < N:
    total += nums[right]
    right += 1

    while total >= S:
        min_length = min(min_length, right - left)
        total -= nums[left]
        left += 1
print(min_length if min_length != N+1 else 0)

이중 while문 구조가 낯설었다.
바깥 while문은 right를 끝까지 순회하기 위한 루프,
안쪽 while문은 누적합이 S 이상일 때마다 현재 구간의 길이를 계산하고, 가능한 구간을 줄이기 위해 left를 이동시키는 구조이다.

이중 while문이지만 시간복잡도는 N^2 이 아니라 최대 2N 이라 O(N)라고 한다.
이 시간복잡도는 아직 와닿지 않는다