[BaekJoon] 백준 알고리즘 1806번 / 부분합 / 투포인터 / Python

문제

 

주의

• 최소 길이를 저장하는 변수인 minLength를 충분히 큰 값으로 지정한다.

 

end 포인터?

• end 포인터는 고정시켜 놓는 것이 아니라, 특정 조건까지 이동시키는 것임.
• 해당 문제는 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 것이 목표임.
• 이때, start 포인터와 end 포인터를 사용하여 특정 조건까지 end 포인터를 이동시키면서 부분합을 계산하고, 그 합이 S 이상이 되는 순간 start 포인터를 이동시켜 최소 길이를 구하는 것임.

 

길이가 0이 될수도 있나?

• for문에서 start를 1씩 증가시키면서 end를 이동시켜 나가다보면 자연스럽게 처리되므로 별도의 처리를 하지 않아도 됨.

 

코드

"""
1. 아이디어
- for문을 통해서 투 포인터로 문제 접근

2. 시간복잡도
- 투 포인터 O(N) : 1e^5 < 2억개 가능!

3. 자료구조
- 수열 저장 list[]
- 부분합 저장 int
- 길이 저장 int
"""

import sys
input = sys.stdin.readline

N,S = map(int, input().split())
A = list(map(int, input().split()))
sum = 0
minLength = float('inf')
end = 0

def solve():
    global sum, minLength, end
    for start in range(N):
        # 특정 조건까지 end 포인터 이동
        while sum < S and end < N:
            sum += A[end]
            end += 1
        # while문을 빠져나와서, 문제의 합과 같은지 확인
        if sum >= S:
            minLength = min(minLength, end - start)
        # 초기화
        sum -= A[start]

solve()
if minLength == float('inf'):
    print( 0 )
else:
    print( minLength )