문제
https://www.acmicpc.net/problem/1806
Algorithm
sum함수를 사용하면 시간이 초과되므로 투포인터 알고리즘으로 처리하되 부분합을 구할 때 누적합에서 누적합을 빼는 방식으로 진행한다. 부분합이 M 이상이 될 때 그 길이의 최솟값을 구한다.
Code
import sys
input = sys.stdin.readline
N, M = map(int, input().split())
array = list(map(int, input().split()))
s = 0
ps = 0
ans = N + 1
i, j = 0, 0
s += array[j]
while j < N:
if s - ps < M:
j += 1
if j < N:
s += array[j]
else:
if i == j:
ans = 1
print(ans)
exit()
if j - i + 1 <= ans:
ans = j - i + 1
ps += array[i]
i += 1
if ans == N + 1:
ans = 0
print(ans)
'Koala - 10기 > 코딩테스트 준비 스터디' 카테고리의 다른 글
[백준/python] 1912 연속합 (0) | 2023.03.29 |
---|---|
[백준/Python] 2638번 치즈 (0) | 2023.03.27 |
[백준 / python] 17609. 회문 (0) | 2023.03.26 |
[백준/Python] 1940 주몽 (0) | 2023.03.26 |
[백준/Python] 14465번: 소가 길을 건너간 이유 5 (슬라이딩 윈도우) (0) | 2023.03.26 |