[Python] 백준 / gold / 1806번 (부분합)

문제 링크 : https://www.acmicpc.net/problem/1806

전형적인 투 포인터 문제였다. for문으로 start 인덱스를 돌리고, 그 안에서 while문으로 적절하게 end 인덱스를 돌려준다. for문을 탈출할 때는 interval_sum에서 현재 start 원소를 반납하는 것을 잊지 말아야한다.

if interval_sum >= S 라는 조건문을 걸지 않아도 문제가 풀리지 않을까? 생각했는데, end가 마지막에 N-1에 걸리고, start와 end 사이의 간격이 좁아지는 상황이라면, interval_sum < S 일 수도 있기 때문에 조건을 반드시 넣어줘야 했다.

정답 코드

import sys
N, S = map(int, sys.stdin.readline().split())
data = list(map(int, sys.stdin.readline().split()))

end = 0
interval_sum = 0
answer = N+1

for start in range(N):
    while end < N and interval_sum < S:
        interval_sum += data[end]
        end += 1

    if interval_sum >= S:
        answer = min(answer, end-start)

    interval_sum -= data[start]

if answer == N+1:
    print(0)
else:
    print(answer)