#342 백준 파이썬 [1806] 부분합 - 투포인터

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

 

SOLUTION

위 문제는 투포인터 알고리즘으로 풀이하면 쉽게 풀린다.

알고리즘은 어렵지 않다.

말그대로 start 포인터와 end 포인터를 활용해 start~end 까지의 합을 구해주는 방식이다.

end는 항상 start를 초과하고 두 포인터 모두 증가하는 방향으로 나아간다.

 

1) 주어진 리스트의 sum_A리스트를 따로 하나 생성한다. (첫항부터 자신 까지의 합이 담긴 리스트)

2) start = 0, end = 1로 놓는다.

3) sum_A[end] - Sum_A[start]를 기반으로 다음 if문을 실행한다.

 

4-0) (start, end)가 (n-1, n)이 되면 종료한다.

4-1) sum_A[end] - sum_A[start] 가 S이상일 경우 answer에 길이를 담아준다. 이후 start에 +1 해주어 다음으로 넘어간다.

4-2) sum_A[end] - sum_A[start] 가 S미만일 경우 end에 +1 해주어 다음으로 넘어간다.

4-3) end가 마지막에 도달했을 경우 start에 +1해준다.

PYTHON CODE

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

#알고리즘 실행
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)