[Python] 1806 부분 합

1. 문제 📚

https://www.acmicpc.net/problem/1806

1806번: 부분합

2. 입출력 예 📋

3. 알고리즘 ✅

투포인터에 응용문제이다 입력이 100,000이 들어오니까 이중포문 돌리면 시간초과날것이다

투포인터 개념만 있다믄 쉽게 푸는 문제이다

4. 소스코드 💻

import sys

input = sys.stdin.readline

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

start, end = 0, 0
internal_sum = 0
answer = 1e9

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

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

    internal_sum -= arr[start]

print(answer if answer != 1e9 else 0)