[백준] 25916번 싫은데요 파이썬

문제

싫은데요 햄스터는 콩쥐를 위해서 깨진 독을 자기 몸으로 막으려고 한다.

햄스터는 유체라 자기 몸을 그림처럼 늘릴 수 있다.

또, 햄스터는 유체라 자기 몸을 아래 그림처럼 늘릴 수도 있다.

하지만 햄스터의 부피는 M$M$으로 정해져 있기 때문에, 늘릴 수 있는 크기에는 한계가 있다.

독에 왼쪽부터 N$N$개의 구멍이 일렬로 뚫려 있고, i$i$번째 구멍의 크기 Ai$A_i$가 주어진다. 햄스터는 구멍을 막기 위해 정확히 그 크기만큼의 부피를 소모해야 한다.

싫은데요 햄스터는 콩쥐에게 최대한 도움이 되길 원하기 때문에 자기 부피를 가능한 한 많이 활용하길 원한다.

어떻게 막으면 햄스터가 원하는 방식으로 독을 막는지 구해서 알려주자.

아무리 햄스터가 유체라고 하지만 몸을 둘로 나눌 수는 없기 때문에 막는 모든 구멍은 연속되어야 한다.

입력

입력은 아래와 같이 주어진다.

 N$N$ M$M$ 

 A1$A_1$ A2$A_2$ ... AN$A_N$ 

출력

구멍을 막는 데에 활용할 수 있는 최대 부피를 출력한다.

제한

•  1≤N≤500000$1\leq N\leq 500,000$ 
•  1≤M≤109$1\leq M\leq 10^9$ 
•  1≤Ai≤109$1\leq A_i\leq 10^9$ 

예제 입력 1

8 10
2 2 2 2 11 2 5 2

예제 출력 1

9

 6$6$번째 구멍부터 8$8$번째 구멍까지 막으면 총 9$9$의 부피를 소모하고, 최대값인 9$9$를 출력한다

제출 답안

'''
1. 아이디어
- 왼쪽부터 계속 값을 누적한다.
- m보다 커지면 그 때까지를 최댓값으로 두고 다시 누적을 시작한다.
2. 시간 복잡도
- 
3. 변수
- num []
'''

import sys
input = sys.stdin.readline

n, m = map(int, input().split())
num = list(map(int, input().split()))

start, end = 0, 1
result = 0
_sum = num[start]
while start < n and end <= n:
    if _sum < m:
        result = max(result, _sum)
        if end == n:
            break
        _sum += num[end]
        end += 1
    elif m < _sum:
        _sum -= num[start]
        start += 1
    else:
        result = m
        break
print(result)