[Python/파이썬] - 백준(BOJ) 1806번 : 부분합

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

1806번: 부분합

 

누적합을 이용하지 않으면 시간초과가 나는 문제이다.

처음에 1 2 3 4 5 를 받는다면 누적합을 구하여 1 3 6 10 15 를 배열에 저장한다

이후 포인터를 두개 생성하여 왼쪽 포인터는 0, 오른쪽 포인터는 1을 가리키게 한다.

그리고 오른쪽 포인터가 가리키는 누적합에서 왼쪽 포인터가 가리키는 누적합을 빼면 사이의 합이 구해진다.

 

이 방식으로 왼쪽 포인터가 배열의 크기를 넘어가지 않을때까지 반복하는데

사이의 합이 m(문제에서는 S)을 넘지 않았을 때 오른쪽 포인터가 배열의 크기를 넘어가지 않으면 오른쪽 포인터를 한칸 증가시키고

넘어간다면 왼쪽 포인터를 한칸 증가시킨다.

그리고 만약 사이의 합이 m을 넘어간다면 answer에 정보를 저장하고 왼쪽 포인터를 한칸 증가시킨다.

 

반복하며 한번도 answer에 정보를 저장하지 않으면 0을 출력하고, 정보를 저장했다면 answer를 출력한다.

 

import sys
input = sys.stdin.readline
n, m = map(int,input().split())
arr = list(map(int,input().split()))
s = [0]
for i in range(n):
    s.append(s[i] + arr[i])
answer = sys.maxsize
l = 0
r = 1
while l < n:
    if s[r] - s[l] < m:
        if r < n:
            r += 1
        else:
            l += 1
    else:
        answer = min(answer, r-l)
        l += 1

if answer == sys.maxsize:
    print(0)
else:
    print(answer)