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

1. 문제 링크

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

1806번: 부분합

2. 풀이

• 분류: 누적합, 투포인터
•  (10 ≤ N < 10만 )과 S (0 < S ≤ 1억) 이므로 O(n)으로 풀어야지, 이중 반복문으론 아무리 break를 걸어도 시간초과 남.
• while 문 1개로 돌리기..
• 누적합 배열 만들어서도 해봤는데 왜 시간초과 나거나 틀렸다고 하는지 모르겠움🤦‍♀️(아직 풀이중)

import sys
input = sys.stdin.readline

n, s = map(int, input().split())
array = list(map(int, input().split()))
length = n

if sum(array) < s: # 0 나오는 예외처리
    length = 0
else:
    lp, rp = 0, 0
    temp = array[lp] # temp: 부분합 담는 변수
    while True: # 반복문 1개로(아니면 시간초과)
        if temp < s:
            rp += 1
            if rp == n: break # 부분합 < s and rp == n인 경우 계산 그만.
            temp += array[rp]
        else:
            length = min(length, rp-lp + 1)
            temp -= array[lp]
            lp += 1

print(length)