[BOJ] 1806 부분합 (python)

부분합 - BOJ

부분합 - BOJ

• 대표적인 투포인터 문제
• 포인터를 두 개 설정(start, end)하여, end를 한 칸씩 늘려가며 target보다 부분합이 작을 때까지만 부분합을 더하고, target보다 커지면 start를 1칸 올려주는 식으로 구현

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

end = 0
summary = 0
shortest_len = float('inf')

for s in range(N):
    while summary < S and end < N:
        summary += li[end]
        end += 1
    if summary >= S:
        shortest_len = min(shortest_len, end - s)
    summary -= li[s]

if shortest_len == float('inf'):
    print(0)
else:
    print(shortest_len)