[ 2003 ] [ 투포인터 ] 수들의 합 2

문제 설명

---

문제

N개의 수로 된 수열 A[1], A[2], …, A[N] 이 있다. 이 수열의 i번째 수부터 j번째 수까지의 합 A[i] + A[i+1] + … + A[j-1] + A[j]가 M이 되는 경우의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다.

출력

첫째 줄에 경우의 수를 출력한다.

---

풀이 과정

1. left를 구간의 왼쪽(포함), right를 구간의 오른쪽(포함 X)으로 둔다.
   • 구간을 왼쪽에서 오른쪽으로 이동시키면서 합계가 M이 되는 구간을 찾는게 목표
2. 만약 구간의 합계가 M보다 크다면, 구간의 합계를 줄여야 하므로 left를 한칸 오른쪽으로 이동시켜서, 구간을 좁힘.
3. 만약 구간의 합계가 M보다 작거나 같다면, 구간의 합계를 늘려야 하므로 right를 한칸 오른쪽으로 이동시켜서 구간을 넓힘.
4. 구간의 합계가 M이라면 갯수를 하나 증가시킨다.

• while문에서 <=로 해야함에 유의. left == right일때도 봐주어야 함. (합계가 0)

---

소스 코드

import sys

input = sys.stdin.readline
N, M = map(int, input().rstrip().split())

sequence = list(map(int, input().rstrip().split()))
left = 0
right = 1
sumation = sequence[left]
answer = 0
while left <= right:
    if sumation == M:
        answer += 1

    # 합계가 M보다 크다면 왼쪽에서 하나 끌고와서 빼준다.
    if sumation > M:
        sumation -= sequence[left]
        left += 1
    # 합계가 M보다 작거나 같다면 오른쪽으로 한칸 늘려준다.
    elif sumation <= M:
        if right == N:
            break
        sumation += sequence[right]
        right += 1

print(answer)