[알고리즘]수들의 합

문제

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

입력1

8 3
1 2 1 3 1 1 1 2

출력1

5

[내 코드]

n,m=map(int,input().split())
a=list(map(int,input().split()))


cnt=p1=0
p2=1
cnt2=0
for num in a:
    if num==m:
        cnt2+=1

while (p1<len(a)):
    if p2<=len(a) and sum(a[p1:p2])==m:
        cnt+=1
        p1+=1
        p2=p1+1
    else:
        if p2<len(a):
            p2+=1
        else:
            p1+=1
            p2=p1+1
            

print(cnt+cnt2)

점수 : 60
1. 시간복잡도 때문에 in4.txt값과 in5.txt값을 출력하지 못함.
2. p1과 p2의 포인터를 통해 리스트로 받은 입력값을 하나씩 더해가면서 이동
3. p1인덱스에서 p2인덱스의 합의 값이 m이면 p1+=1를 통해 포인터 이동

[해설코드]

n,m=map(int,input().split()))
a=list(map(int,input().split()))
lt=0
rt=1
tot=a[0]
cnt=0
while True:
	if tot<m:
    	if rt<n:
    		tot+=a[rt]
        	rt+=1
    	else:
    		break
   elif tot==m:
   		cnt+=1
        tot-=a[lt]
        lt+=1
   else:
   		tot-=a[lt]
        lt+=1
print(cnt)