[Python] 25916번 싫은데요

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

25916번: 싫은데요

---

 

22/11/06

 

 

전형적인 투 포인터 문제로, 대회 도중에 쉽게 풀 수 있었다.

---

 

문제 접근 방식:

 

 

 

햄스터의 머리를 end포인터라고 하고, 햄스터의 꼬리를 start포인터라고 하자.

 

햄스터의 몸을 한 칸씩 늘리는 것은 end포인터를 뒤로 한 칸씩 당기는 것과 같다.

 

 

그러면, 생각을 한번 해보자.

 

우리는 햄스터가 몸을 늘릴 수 있을 만큼 최대한 늘리고 싶다는 사실을 아주 잘 안다.

 

그 말인즉슨, 한 칸을 만약에 늘릴 수 있을 때(몸을 늘릴 수 있는 공간이 있을 때) 햄스터가 괜찮다면(햄스터가 그 구멍을 막을 수 있다면), 늘려야 된다.

 

만약 한 칸을 늘릴 수 있을 때(몸을 늘릴 수 있는 공간이 있을 때), 햄스터가 그 칸을 막을 수 없다면(부피가 넘어간다면), 늘릴 수가 없다.

때문에 햄스터의 꼬리를 한 칸 당김으로써 부피를 더 만들어줘야 된다.

 

 

이를 투 포인터의 개념으로 생각하면, 만약 다음 칸을 햄스터가 채울 수 있으면 몸을 늘리므로 end인덱스를 1 늘리면 된다.

 

그리고 현재 햄스터가 막고 있는 부피에 그 인덱스에 해당하는 원소의 값만큼을 추가해주면 된다.

 

다음 칸을 채울 수 없으면 몸을 줄여야 되므로 start인덱스를 1 늘리면 된다.

 

그리고 현재 햄스터가 막고 있는 부피에 그 인덱스에 해당하는 원소의 값만큼을 빼주면 된다.

 

이 과정을 반복하다가 햄스터가 더 이상 몸을 늘릴 수 있는 공간이 없으면, 다시 말해 end인덱스를 늘려야 되는데 인덱스를 못 늘릴 때(IndexError가 날 때) 종료해주면 된다.

---

아래는 내가 위의 접근 방식과 같이 작성한 파이썬 코드이다. 더보기를 누르면 확인할 수 있다.

# 싫은데요
import sys
input = sys.stdin.readline

N, M = map(int, input().rstrip().split())
arr = list(map(int, input().rstrip().split()))
start_idx = 0
end_idx = 1
val = sum(arr[start_idx:end_idx])
max_val = 0
while True:
    try:
        if val <= M:
            if val > max_val:
                max_val = val
            val += arr[end_idx]
            end_idx += 1
        else:
            val -= arr[start_idx]
            start_idx += 1
    except IndexError:
        break
print(max_val)