[백준 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

4 2
1 1 1 1

예제 출력 1

3

예제 입력 2

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

예제 출력 2

3

 

문제풀이

import sys

n,m=map(int, sys.stdin.readline().split(' '))
numbers=list(map(int, sys.stdin.readline().split(' ')))
ans=0
end=0
cur=0
# 투 포인터
for start in range(n):
    # 일종의 완전 탐색 방식 -> pypy에서만 패스
    # cur_sum = numbers[start]
    # if cur_sum == m:
    #     ans += 1
    # for end in range(start + 1, n):
    #     if cur_sum >= m:
    #         break
    #     cur_sum = cur_sum + numbers[end]
    #     if cur_sum == m:
    #         ans += 1
    while cur<m and end<n:
        cur+=numbers[end]
        end+=1
    if cur==m:
        ans+=1
    cur-=numbers[start]

print(ans)

주석 처리된 코드는 pypy에선 통과하지만 python에선 시간초과가 발생했다. 주석 처리된 코드는 사실상 거의 완전 탐색이나 다름없었다.

볼펜으로 끄적여 본거라 잘 알아볼 수 있으실진 모르겠지만ㅠㅠ.. start를 0에서 n-1까지 부여하고, end=start+1로 초기화해준 후에

for문을 돌면서 지금까지 지나온 값을 모두 합한 cur_sum값이 m보다 커질 경우 break하고, m과 같을 경우 ans+=1해주는 방식이다.

start가 0일 때 cur_sum=numbers[0]으로 초기화되고, end=1로 초기화된다. 그리고 end가 n보다 작을 때까지 numbers[end]를 cur_sum에 더해주면서 for문을 반복하게 되는데(1+2+3+...) 반복 도중에 m값인 5보다 커지면 break된다. 

결국 모든 start 지점에서부터 다음 요소들을 m보다 커지거나 같아질 때까지 반복해서 더하는 것이다. 

 

그래서 매번 새로운 start를 시작할 때마다 cur_sum과 end값을 새로 초기화해주는 것이 아니라, 기존의 cur_sum 값에서 numbers[start]을 빼주고, 다시 cur_sum 값이 m보다 작고, end 값이 n보다 작을 때까지 cur_sum+=numbers[end]를 해주는 방식으로 변경했다. 

cur_sum이 m과 동일한 경우엔 ans+=1을 해주면 된다.