백준 1806 부분합 파이썬
접근
- 정해진 길이가 없기에 사이즈가 자유로운 윈도우 사이즈로 수열을 탐색한다.
- 앞의 포인터를 post, 뒤를 pre라 할때 윈도우의 합이 S 보다 커질때까지 post가 앞으로 움직인다.
- 윈도우 합이 S 보다 작을때까지 pre가 앞으로 움직인다.
- 움직임이 끝나면 현재 윈도우 길이가 최소 길이보다 짧은지 비교한다.
사고
O(N) 풀이법이 쉽게 떠오른데 비해 정답률이 낮아서 의아했다. 하지만 나도 코너 케이스와 조건문 처리에서 몇번 틀려서 다시 제출했다. 몇번 고쳐서 넣으면 답이 나오긴 하는데 처음 접근에서 더 많은 경우의 수를 고려하는 연습이 필요한 것 같다.
import sys
input = sys.stdin.readline
N, S = list(map(int, input().split()))
m = list(map(int, input().split()))
ans = sys.maxsize
prep = 0
postp = 0
s = 0
while (prep < N or postp < N):
while postp < N and s < S:
s += m[postp]
postp += 1
while prep < N and s >= S:
s -= m[prep]
prep += 1
ans = min(ans, postp - prep + 1)
if postp == N and s < S:
break
if sum(m) < S:
print(0)
else:
print(ans)
