[투포인터 / python] 백준 25916. 싫은데요

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

25916번: 싫은데요

 

첫 번째 풀이

 

우선, 조건에 따라 '연속'된 구멍의 '합'이 햄스터의 부피보다 작아야 하므로 투포인터로 풀면 되겠다고 판단했다.

 

이제 로직을 구성하면 되는데, 일정 연산 결과가 조건보다 작으면 냅다 오른쪽 포인터를 진행시키는게 일반적이라 생각했는데, 이번 문제에서는 포인터가 가리키는 범위의 합이 항상 햄스터의 부피 이하여야 하므로 오른쪽 포인터를 진행한 상황에서의 값이 몇인지 체크하고, 부피 이하로 들어올 경우 오른쪽 포인터를 진행시킨 뒤에 max 값(이후 결과값)을 저장했다. 이를 통해 모든 경우에서 가장 컸던 합을 출력하면 문제에서 원하는 답이 된다.

 

결과 : 성공

 

import sys
input = sys.stdin.readline

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

left, right = 0, 1
sum = li[left]
mx = 0
while True:
    if right >= n: break

    if right < n:
        if sum+li[right] <= m:
            sum += li[right]
            mx = max(mx, sum)
            right += 1
        elif sum+li[right] > m:
            sum -= li[left]
            left += 1
print(mx)