[알고리즘] 25916 싫은데요(Python)

문제분석

문제

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

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

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

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

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

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

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

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

예제

코드 분석

경우처리

if n==1 and hole[0]<=m:
    print(hole[0])
    exit(0)
elif n==1 and hole[0]>m:
    print(0)
    exit(0)

투포인터 문제이지만 적용되지 않는 경우가 있다. 바로 n=1인 경우
start와 end로 나머지 경우는 처리가 가능하지만 n=1로 오게 되면 start와 end가 일치하지 않는 문제가 발생하게 된다. 이를 위해 먼저 처리를 해주어야 한다.
n=1이고 m보다 작거나 같으면 구멍크기만큼 출력하고 종료한다.
이 문제를 풀 때 만약 구멍 크기보다 m이 크면 어떻게 처리해야하지 싶었는데 0으로 처리한다.
그리고 여기서는 exit(0)으로 마무리를 해주어야 한다.

물론 뒤에 나오는 나머지 코드를 else로 묶어서 보내도 되긴 하지만 그렇게 만들지 않고 만들려면 exit(0)으로 마무리해주면 된다.

시작점 크기 기록

if hole[0]<=m:
    result+=hole[0]

구멍 크기가 최대크기보다 작다면 기록하고 시작하면 된다. 아니라면 반복문내에서 start값을 올리면서 위치를 찾을 것이다.

최대 부피 구하기

while start<=end and end<=n-1:
    if result+hole[end]<=m:
        result+=hole[end]
        end+=1
    elif result+hole[end]>m:
        if hole[end]>m and end+1<=n-1:
            result=0
            start=end+1
            end+=1
        else:
            result-=hole[start]
            start+=1
    answer=max(answer,result)

그럼 반복문을 살펴보자.
반복문이 조금 복잡하게 생겼다. 투포인터의 특징을 그대로 가지는 느낌이다. 먼저 투포인터란 뭔지 아는것이 필요하다. 두개의 점을 위치를 기록하면서 처리하는 알고리즘이다.
while문은 start가 end보다 작거나 같으면서도 end은 n-1까지만 접근하면서 찾아나가야하므로 while문에 조건을 걸어주었다.
그리고나서 end위치 값을 더해 m보다 작거나 같으면 기록하고 end 위치를 옮기게 된다. 만약 end위치를 더했는데 m보다 크다. 그러면 두가지로 찾아봐야 한다.
이제 여기선 result값을 초기화를 시킬 것인가, 아니면 start위치 값을 바꿔줄 것인가가 필요하기 때문이다. elif 내에서 다시 조건문으로 나눈다. 하나는 end위치 자체 값이 최대 부피보다 큰경우를 말하는데 이때에는 무조건 초기화 시키고 start값을 바꿔준다. 그전까지의 결과는 max비교를 통해 넣었을 것이기 때문에 상관없다. end위치의 자체값이 m보다 작거나 같으면 start위치를 하나씩 올리면서 체크를 하면 되므로 이렇게 처리를 해준다.
그리고 max값을 기록해나가면서 반복문을 돈다.

최종 코드

n,m = map(int,input().split())
hole=list(map(int,input().split()))
start=0
end=1
result=0
answer=0
if n==1 and hole[0]<=m:
    print(hole[0])
    exit(0)
elif n==1 and hole[0]>m:
    print(0)
    exit(0)
if hole[0]<=m:
    result+=hole[0]
while start<=end and end<=n-1:
    if result+hole[end]<=m:
        result+=hole[end]
        end+=1
    elif result+hole[end]>m:
        if hole[end]>m and end+1<=n-1:
            result=0
            start=end+1
            end+=1
        else:
            result-=hole[start]
            start+=1
    answer=max(answer,result)
print(answer)

최종 코드는 다음과 같다.

결론

투포인터, 처음에는 뭐였더라 했는데 개념을 살펴보니 알고리즘 시간에 정렬 공부할 때 했던 것이 기억났다.
이 문제를 보면서 대충 느낌은 알겠는데 어떻게 짜야하지 생각이 들었다. 투포인터를 바로 떠올리지 못한 탓이다. 그리고 조건문도 나누는 방법 역시 헷갈렸다. 자주 짜보면서 다시 감을 찾아야 할 필요가 있는 것 같다.
다음에 다시 풀어봐야겠다!