BOJ 1806 부분합

1. BOJ 1806 부분합 

골드 4, 누적합, 투포인터

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

코드

import sys
input = sys.stdin.readline
N, S = map(int, input().split())
arr = list(map(int, input().split()))
 
sum_value = 0
prefix_sum = [0]
for i in arr:
    sum_value += i
    prefix_sum.append(sum_value)
 
right, interval_sum, ans = 0, 0, 0
for left in range(N):
    while (prefix_sum[right]-prefix_sum[left])<S and right<N:
        right +=1
    if (prefix_sum[right]-prefix_sum[left])>=S:
        if ans==0:
            ans = (right-left)
        else:
            ans = min(ans, right-left)
 
print(ans)

설명

이 문제는 "합이 S 이상"이 되는 것 중 가장 짧은 것을 구하는 것이다. 

따라서 대표적인 예시로,
10 10
3 3 3 3 3 3 3 3 3 3
의 출력이 '4' 가 나온다. 

누적합 배열 (prefix_sum)을 만들고, 투 포인터를 사용해서 풀 수 있었다. 그냥 투포인터를 사용해서 완탐을 시도했을 때 '시간초과'가 뜨기 때문에, 누적합을 써야한다.
각 구간의 합도 sum(arr[left : right])을 쓰지 않고, prefix_sum[right]-prefix_sum[left]로 계산하였다.