[BaekJoon] 백준 알고리즘 2003번 / 수들의 합 2 / 투포인터 / Python

 

간단한 투 포인터 알고리즘을 이용하여 풀 수 있습니다. 시작점(start)과 끝점(end)을 이용하여 구간합(interval_sum)을 구하며 end를 이동시키며 구간합이 M과 같아지면 카운트합니다. start를 이동시키면서 구간합(interval_sum)도 갱신합니다. 이 알고리즘의 시간 복잡도는 O(N)입니다.

"""
1. 아이디어
- 투 포인터를 통한 계산
2. 시간복잡도
- O(N) : 10,000 < 2억개!, 출력 가능
3. 자료구조
- 수열 저장 int[]
- 합계 저장 int
- 경우의 수 저장 int
"""

import sys

input = sys.stdin.readline

N, M = map(int, input().split())
A = list(map(int, input().split()))

count = 0
interval_sum = 0
end = 0

for start in range(N):
    # end 포인터 이동
    while interval_sum < M and end < N:
        interval_sum += A[end]
        end += 1

    # 부분합이 M과 같으면 카운트
    if interval_sum == M:
        count += 1

    # start 포인터 이동에 따른 interval_sum 갱신
    interval_sum -= A[start]

print(count)