[python] 백준 1806번 부분합

백준 1806번 부분합

https://www.acmicpc.net/problem/1806

문제

풀이

import sys
input = sys.stdin.readline
n,s = map(int, input().split())
data = list(map(int, input().split()))

end = 0
current_sum = 0
count = 0
answer = []

for start in range(n):
    while current_sum < s and end < n:
        current_sum += data[end]
        end += 1
    # 부분합 중에 그 합이 S 이상이 되는 것 
    if current_sum >= s:
        answer.append(end-start) # end 가 항상 다음 요소를 가르키고 있다
    current_sum -= data[start]

if answer == []:
    print(0)
else:
    print(min(answer))

📌 주의

• 부분합 중에 그 합이 S 이상이 되는 것 (당연히 부분합 == S인 줄... 문제 잘 읽자)
• 투포인터는 start, end 가 동시에 0에서 시작하는 것도 있고, start 는 0, end 는 n-1 에서 시작하는 것도 있다.