문제
싫은데요 햄스터는 콩쥐를 위해서 깨진 독을 자기 몸으로 막으려고 한다.
햄스터는 유체라 자기 몸을 그림처럼 늘릴 수 있다.
또, 햄스터는 유체라 자기 몸을 아래 그림처럼 늘릴 수도 있다.
하지만 햄스터의 부피는 M으로 정해져 있기 때문에, 늘릴 수 있는 크기에는 한계가 있다.
독에 왼쪽부터 N개의 구멍이 일렬로 뚫려 있고, i번째 구멍의 크기 Ai가 주어진다. 햄스터는 구멍을 막기 위해 정확히 그 크기만큼의 부피를 소모해야 한다.
싫은데요 햄스터는 콩쥐에게 최대한 도움이 되길 원하기 때문에 자기 부피를 가능한 한 많이 활용하길 원한다.
어떻게 막으면 햄스터가 원하는 방식으로 독을 막는지 구해서 알려주자.
아무리 햄스터가 유체라고 하지만 몸을 둘로 나눌 수는 없기 때문에 막는 모든 구멍은 연속되어야 한다.
입력
입력은 아래와 같이 주어진다.
N M
A1 A2 ... AN
출력
구멍을 막는 데에 활용할 수 있는 최대 부피를 출력한다.
제한
- 1≤N≤500000
- 1≤M≤109
- 1≤Ai≤109
예제 입력 1 복사
8 10
2 2 2 2 11 2 5 2
예제 출력 1 복사
9
6번째 구멍부터 8번째 구멍까지 막으면 총 9의 부피를 소모하고, 최대값인 9를 출력한다
출처
University > 연세대학교 > 2022 연세대학교 프로그래밍 경진대회 C번
알고리즘 분류
# https://www.acmicpc.net/problem/25916
'''
1. 아이디어 :
1) 연속된 최대합을 구하는 문제다. 투포인터로 풀 수 있다. while문 rp가 오른쪽 끝까지 갈때까지
안에서 lp[0], lp[1]로 target보다 작으면 lp+=1, 아니면 rp+=1, 같으면 lp+=1, rp+=1로 풀 수 있다.
2. 시간복잡도 :
1) O(n)
3. 자료구조 :
1) 배열
'''
import sys
input = sys.stdin.readline
n, target= map(int, input().split())
nums = list(map(int, input().split()))
cmax, total, lp, rp = 0, nums[0], 0, 0
while rp < n - 1:
if total < target:
rp += 1
total += nums[rp]
elif total > target:
total -= nums[lp]
lp += 1
elif total == target:
rp += 1
total += nums[rp]
total -= nums[lp]
lp += 1
if total <= target:
cmax = max(cmax, total)
print(cmax)'알고리즘 문제 > 백준' 카테고리의 다른 글
| 최솟값 찾기 #11003 (1) | 2023.01.14 |
|---|---|
| 연속하는 소수의 합 #7512 (1) | 2023.01.14 |
| 동전 0 #11047 (0) | 2023.01.13 |
| 퇴사 #14501 (1) | 2023.01.13 |
| 팰린드롬? #10942 (1) | 2023.01.13 |