문제

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

입력

4 2
1 1 1 1

출력

3

예제 2

입력

10 5
1 2 3 4 2 5 3 1 1 2

출력

3

---

풀이

각 인덱스까지의 합을 계산한 arr_prefixSum 배열을 만든다.
구간의 처음을 나타내는 idx_start를 만들고 0으로 초기화 한다.

arr_prefixSum을 순회하면서 저장된 합이 주어진 합과 동일한지 비교한다.

같으면 count를 증가시키고 다음 인덱스를 검사한다.
적어도 다음 인덱스를 검사한다.
값이 클 경우, 즉 주어진 합보다 arr_prefixSum[idx]에 저장된 합이 더 클 경우가 중요한데 현재까지의 합 arr_prefixSum[idx]에서 처음 더해진 요소 arr_prefixSum[idx_start] 값을 차례로 차감시키면서 합이 같은지 비교해야 한다.

idx가 arr_ele의 마지막 요소를 검사하고 나면 모든 검사가 완료된 것이다.
최종 count를 출력한다.

소스

파이썬으로 작성하였다.

_sum = int(raw_input().split(' ')[1])
arr_ele = [ int(x) for x in raw_input().split(' ')]

arr_prefixSum = []
cur = 0
for x in arr_ele:
	cur += x
	arr_prefixSum.append(cur)

idx_start = 0
idx = 0
sub = 0
count = 0

while idx < len(arr_ele):
	cur = arr_prefixSum[idx] - sub
	if cur == _sum:
		count += 1
		idx += 1
	elif cur > _sum:
		sub = arr_prefixSum[idx_start]
		idx_start += 1
	else:
		idx += 1
print count