[백준 1806] 부분합

1. 요약

10,000 이하의 자연수로 이루어진 길이 N짜리 수열이 주어진다. 이 수열에서 연속된 수들의 부분합 중에 그 합이 S 이상이 되는 것 중, 가장 짧은 것의 길이를 구하는 문제.

2. 아이디어

누적합과 투 포인터를 이용하여 해결한다. 조건에 따라 start 포인터와, end 포인터가 유동적으로 움직이기 때문에, 사전에 누적합을 구하고, 이후 투 포인터로 접근하여 해결한다.

3. 코드

import sys
n, s = map(int, sys.stdin.readline().rsplit())
arr = list(map(int, sys.stdin.readline().rsplit()))
INF = int(1e9)
answer = INF
start, end = 0, 0
table = [0] * (n+1)

for i in range(n): table[i+1] = table[i] + arr[i]

while end < n:
    seq_total = table[end+1] - table[start]
    if seq_total >= s:
        answer = min(end - start + 1, answer)
        if start == end: end += 1
        else: start += 1

    else: end += 1

if answer != INF: print(answer)
else: print(0)