[BOJ/백준] 1806번 부분합 - Python/파이썬 [해설/풀이]

📌 문제

---

📝 입력

---

💻 출력

---

📖 예제 입출력

---

📌 풀이

---

📖 해설

---

부분합, 누적합 알고리즘을 이용하는 문제
모든 부분합을 Big-O(1)의 시간복잡도로 구할 수 있다

💻 전체코드

---

import sys
input = sys.stdin.readline

N, S = map(int, input().split())
sequence = list(map(int, input().split()))

prefix = [0] * (N + 1)								# 누적합
for i in range(1, N + 1):							# 1부터 N+1까지임에 주의
    prefix[i] = prefix[i - 1] + sequence[i - 1]		# prefix[i]는 sequence[i-1]까지의 누적합을 의미

answer = 100001								# 길이 N의 최대값 = 100,000
start, end = 0, 1							# 부분합의 범위를 지정할 start, end
while start < N:							# 모든 부분합에 대해 확인해보아야 하므로
    if prefix[end] - prefix[start] >= S:	# start ~ end까지의 부분합 >= S이면
        answer = min(answer, end - start)	# end - start = 부분합의 길이
        start += 1							# start + 1
    else:					# start ~ end까지의 부분합 < S이면
        if end < N:			# end가 주어진 수열의 길이를 벗어나지 않는 이상
            end += 1		# end를 먼저 뒤로 이동
        else:				# end가 주어진 수열의 길이의 최대값에 도달했다면
            start += 1		# start를 뒤로 이동

if answer == 100001:		# 합이 S이상인 부분합을 만드는 것이 불가능한 경우
    answer = 0				# answer = 0
print(answer)