[백준 2003] 수들의 합

1. 요약

N개의 수로된 수열 A[1], A[2], ..., A[N]이 있을 때, i번째 수부터 j번째 수까지의 합, A[i] + A[i+1] + A[i+2] + .. + A[j]가 M이 되는 경우의 수를 구하는 문제

2. 아이디어

투 포인터를 이용하여 해결했다.
배열 A의 인덱스를 가리키는 start 포인터, end 포인터를 두고 start 포인터 가리키는 인덱스 <= end 포인터가 가리키는 인덱스를 유지하면서 start 포인터가 가리키는 배열 A값부터 end 포인터가 가리키는 배열 A값까지 더한다.

만약 결과가 같으면 카운트를 하고 M보다 작으면 end 포인터를 다음 위치로 이동한다.(i.e. 더한 결과가 M보다 작게 나왔기 때문에, end 포인터를 다음위치로 이동함으로써 향후 더한 결과를 이전 결과보다 크게 만들 수 있다.)

반대로 더한결과가 M보다 크면 start 포인터를 다음 위치로 이동한다. 따라서 향후 더해서 나오는 결과는 이전에 나왔던 결과보다 작을 것이다.

위의 과정을 end 포인터가 가리키는 인덱스가 N이 될 때까지 위의 과정을 수행한다.

3. 코드

import sys

n, m = map(int, sys.stdin.readline().rsplit())
arr = list(map(int, sys.stdin.readline().rsplit()))
sp, ep = 0, 0
answer = 0

while ep < n:
    total = sum(arr[sp:ep+1])
    if total == m:
        answer += 1
        ep += 1
    elif sp == ep or total < m: ep += 1
    else: sp += 1

print(answer)