[BOJ/Python] 25916_싫은데요

문제 출처:https://www.acmicpc.net/problem/25916

25916번: 싫은데요

 

문제

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

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

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

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

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

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

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

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

입력

입력은 아래와 같이 주어진다.

 N M 

 A1 A2 ... AnN

출력

구멍을 막는 데에 활용할 수 있는 최대 부피를 출력한다.

제한

•  1≤N≤500,000
•  1≤M≤10**9
•  1≤Ai≤10**9

예제 입력 1

8 10
2 2 2 2 11 2 5 2

예제 출력 1

9

 6번째 구멍부터 8번째 구멍까지 막으면 총 9의 부피를 소모하고, 최대값인 9를 출력한다

 

---

풀이

 

연속된 구멍을 막을 수 있는 최대 부피를 구해야 하므로, 투 포인터를 이용하여 M이하의 연속된 수의 합을 구하여 문제를 해결하였다.

투 포인터를 이용하여 예제 입력 1을 풀어보면 다음과 같다.

우선 start, end 포인터 두 개를 만든다. (빨간색 포인터 = start, 파란색 포인터 = end)

 

파란색 포인터를 한 칸 오른쪽으로 이동시킨다. 현재 sum=2가 되고, M보다 작으니 계속 파란색 포인터를 이동시킨다.

아직 M보다 작으므로 한 칸 더 이동시킨다.

한 칸 더 이동한다.

한 칸 더 이동한다.

여기서 sum이 M보다 크므로, 바로 이전 단계까지 구한 sum을 이용하여 max_sum을 구한다.

여기서는 기존의 max_sum이 없었으므로 이전 단계까지 구한 sum이 max_sum이 된다.

sum이 M보다 크므로 start포인터를 한 칸 이동시킨다.

sum이 M보다 작아졌으므로, end포인터를 이동시킨다.

end포인터가 리스트의 끝에 도달하였고, sum이 M보다 작다.

여기서 sum의 값은 더 이상 늘릴 수 없고, start포인터를 오른쪽으로 이동시켜 봤자 sum 값이 줄어들기 때문에 이동시킬 필요가 없다.

따라서 여기서 기존의 max_sum과 sum을 비교하여 더 큰 값을 max_sum으로 설정하고, break 한다.

그리고 만약 중간에 sum==M인 경우를 발견한다면, 최대의 경우를 발견하였으므로 max_sum을 M값으로 설정하고 break 한다.

 

코드는 다음과 같다.

 

import sys
 
n,m = map(int,sys.stdin.readline().split())
n_list = list(map(int,sys.stdin.readline().split()))
 
end = 0
sum = 0
max_sum = 0
for start in range(n):
    while end<n and sum<m:
        sum+=n_list[end]
        end+=1
 
    if sum==m:
        max_sum = m
        break
    elif end==n and sum<m:
        max_sum = max(max_sum,sum)
        break
    else:
        max_sum = max(sum-n_list[end-1],max_sum)
 
    sum-=n_list[start]
    
print(max_sum)