[Python] 부분합 - 백준 (투 포인터)

해당 글은 백준 1806번 '부분합' 문제를 다룬다.

문제

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

1806번: 부분합

 

설명

처음엔 시간 제한이 0.5초여서 안될 것 같았지만, 배열의 start~end까지 슬라이스로 인덱스 접근을 이용하여 풀었는데 시간초과가 발생했었다.

시간을 단축할 수 있는 방법으로 투 포인터 알고리즘이 있다.

start와 end의 투 포인터 변수를 생성하고, start과 end 위치에 따른 total이 s보다 작다면, end 포인터를 이동시키고

total이 s보다 크거나 같다면, 최소의 길이의 부분합을 찾아야 하므로 start 포인터를 이동시켜 다시 탐색한다.

그리고 total이 s보다 작으면서 end 포인터가 n이 된다면, while 문을 종료시키고 결과값을 출력시키면 된다.

 

코드

n, s = map(int, input().split())
arr = list(map(int, input().split()))

start, end = 0, 0
answer = int(1e9)
total = 0
while True:
    if total >= s:
        answer = min(answer, end-start)
        total -= arr[start]
        start += 1
    elif end == n:
        break
    else:
        total += arr[end]
        end += 1
if answer == int(1e9):
    print(0)
else:
    print(answer)