백준 2003: 수들의 합 2 - 투 포인터(파이썬)

수들의 합 2 성공

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을 넘지 않는 자연수이다.

출력

첫째 줄에 경우의 수를 출력한다.

 

내 코드

 

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

start, end=0, 1
cnt=0

while end<=n: #end는 n까지 가능. arr[?:n]이면 arr[n-1]까지 접근하는 것임.
    tmp_sum=sum(arr[start:end]) #계속 바뀌는 시작~끝의 합 tmp_sum

    if tmp_sum<=m: #합이 목표치보다 작거나 같으면,
        if tmp_sum==m: #같으면 cnt+=1
            cnt+=1
        end+=1 #공통적으로 end를 한칸 전진
    else: #합이 목표치보다 크면,
        start+=1 #start를 한칸 전진

print(cnt)

 

풀이 및 접근)

- 투 포인터를 이용한 문제이다.

 

*아래의 링크를 참고했다

https://code-lab1.tistory.com/276

[알고리즘] 투 포인터 알고리즘(Two-Pointers Algorithm)이란? 백준 2003번 C++ 풀이