[백준]수들의합2(python)

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

2003번: 수들의 합 2

문제 요약

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

문제유형

투포인터

아이디어

1. start, end 라는 두개의 포인터를 사용
2. start는 앞부분 end는 뒷부분을 가르킴
3. 부분합 배열의 합 < 구해야 하는값 end를 오른쪽으로 한칸 이동 부분합 배열의 합 >= 구해야 하는값 start를 오른쪽으로 한칸 이동

코드

import sys
input = sys.stdin.readline
n,m = map(int,input().split())
num = list(map(int,input().split()))

start = 0
end = 0
cnt = 0
sums = 0


while True:
    if sums >= m:
        sums -= num[start]  # 부분합배열의합 >= 구해야하는 값 : start를 오른쪽으로 한칸이동하여 부분합배여크기 감소
        start += 1
    elif end == n: # end가 n 이되면 종료
        break
    else:
      sums += num[end] # 부분합배열의합 <= 구해야 하는 값 : end를 오른쪽으로 한칸 이동하여 부분합 배열의 크기를 증가
      end += 1

    if sums == m:
        cnt += 1
print(cnt)