[백준] 25916 - 싫은데요 (파이썬)

문제 링크

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

문제 요약

햄스터는 유체라 자신의 부피를 늘려서 일정한 구멍을 막을 수 있지만, 부피 M 안에서만 활용할 수 있습니다. 왼쪽부터 N개의 구멍이 일렬로 뚫려 있으며, 각 구멍의 크기 A_i​가 주어집니다. 햄스터는 자신이 가진 최대 부피 M 안에서 가능한 한 많은 연속된 구멍을 막고자 합니다. 모든 구멍은 연속적으로 막아야 하며, 각 구멍을 막을 때는 해당 구멍의 크기만큼 부피가 필요합니다.

푼 방법

 

• **슬라이딩 윈도우 (투 포인터)**를 활용하여 왼쪽 포인터 i와 오른쪽 포인터 j를 두고, 두 포인터가 특정 범위를 이루도록 조정하면서 조건을 만족하는 최대 부피의 구간을 찾습니다.
• 만약 현재 위치의 구멍 크기가 M보다 크다면, 햄스터는 막을 수 없으므로 포인터를 이동하여 조건을 다시 맞춥니다.
• 각 윈도우 구간의 부피의 합을 계산하면서 최대값을 기록하고, 최종적으로 이 값이 최대 부피가 됩니다.

 

정답 코드

n, m=map(int, input().split())
holes = list(map(int,input().split()))
result=[]
i=0
j=0
while i<=j and j<n:
    sum=0
    left=m
    while i<=j and j<n:
        if holes[j]>m:
            j+=1
            i=j
            result.append(sum)
            break
        elif left>=holes[j] and m>=holes[j]:
            sum+=holes[j]
            left-=holes[j]
            j+=1
        else:
            sum-=holes[j]
            result.append(sum)
            i=j
            break

print(max(result))

배웠던 부분

• 슬라이딩 윈도우 (Sliding Window): 특정 조건을 만족하는 연속적인 구간의 합을 빠르게 찾기 위해 사용합니다. 이 문제에서는 O(N)O(N)O(N) 시간 복잡도로 전체 구멍 배열을 순회하면서 조건을 만족하는 최대 부피 구간을 찾을 수 있습니다.