[BOJ, 백준] 1806 부분합 Python

 

부분합 전통적인 문제입니다.

 

문제에서 S "이상" 이라는 것을 못보고 뻘짓하느라 오답을 마구마구 제출했네요 ,,,

 

코드는 이하와 같습니다.

 

prefix_sum의 i번째 원소를 num[i]까지의 합이라고 하면

num_i 부터 num_j까지의 합은 prefix_sum[j] - prefix_sum[i-1] 가 됩니다.

이를 활용하면 다음과 같습니다.

import sys
input = sys.stdin.readline

N,S = map(int,input().split())
num = list(map(int,input().split()))
prefix = [0]
for i in range (0,N):
    prefix.append(prefix[-1] + num[i])
    
answer = []
l,r = 0,1
while l < r and r != N+1:
    partial_sum = prefix[r] - prefix[l]
    if partial_sum >= S:
        answer.append(r-l)
        l += 1
    elif partial_sum < S:
        r += 1


answer.sort()

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