백준 25916 : 싫은데요 (Python)

본문 링크

import sys
input=sys.stdin.readline

N,M=map(int,input().split())
L=list(map(int,input().split()))

start = 0 ; end=1 ; answer=0 ; total=0

if N==1 and L[0]<=M:
    print(L[0])
    exit(0)
elif N==1 and L[0]>M:
    print(0)
    exit(0)

if L[start]<=M:
    total+=L[start]
while start<=end and end<=N-1:
    if total+L[end]<=M:
        total+=L[end]
        end+=1
    elif total+L[end]>M:
        if L[end]>M and end+1<=N-1:
            start=end+1 ; end+=1 ; total=0
        else:
            total-=L[start]
            start+=1
    answer=max(answer,total)

print(answer)

📌 어떻게 접근할 것인가?

연속으로 막을수 있는 구멍의 최대값을 찾는 문제이다.
누적합으로도 풀수있을것같으나 좀더 익숙한 투 포인터로 풀기로 했다.

📌 어떻게 투 포인터를 적용할 것인가?

start 와 end 를 1 로 잡는다. 만약 햄스터가 오른쪽 구멍을 막을 수 있으면 end 값을 증가시킨다.
그렇지 않으면 start 값을 증가시켜서 가장 많은 부피를 막을수 있는 값을 구한다.
하지만 문제에서 까다로운점은 구멍하나가 햄스터 크기보다 클 수 있다는 점이다.
이떄는 if L[end]>M and end+1<=N-1 예외 처리를 해주어서 그냥 2칸을 이동하는 식으로 예외처리 해주면된다.

answer=0 으로 잡고 매번 움직일때마다 total 과 자기자신중 더 큰값을 적용시킨다.

✅ 코드에서 주의해야할 부분

• N==1 일떄 구멍을 막을수있는지 없는지 예외처리를 해준다.
• start=0 , end=1 로 잡는다.
• 처음 start 구멍을 막을 수 있다면 total 변수에 값을 더해준다.
• 투 포인터지만 구멍을 하나만 막을 수 있기때문에 while 문 조건을 start<=end and end<=N-1 로 설정한다.