[백준] 1806번 부분합 - 파이썬

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

1806번: 부분합

문제

부분합이 무엇인지에 대해서 짚고 넘어가겠다.

부분 합은 구간 합과 달리 처음부터 특정인덱스까지의 합을 의미한다. 구간합과 다르니 주의하길바란다.

입력

첫번째 줄 => N: 주어진 원소의 개수 S: 부분합은 S 이상이어야 출력이 가능하다.

두번째 줄 => 수열

풀이

부분합 리스트를 만들어준 뒤 투포인터 알고리즘을 이용해서 풀어주었다.

# 1806번 연속합
N, S = map(int, input().split())
A = list(map(int, input().split()))

# 먼저 0~n까지의 합을 구해줌
sum_A = [0] * (N+1)
for i in range(1, N+1):
    sum_A[i] = sum_A[i-1] + A[i-1]

answer = 1000001
start = 0
end = 1

# S가 끝으로 갈 때까지 계산
while start != N:
    if sum_A[end] - sum_A[start] >= S:
        if end - start < answer:
            answer = end - start
        start += 1
    
    else:
        if end != N:
            end += 1
        else:
            start += 1

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

출력결과