백준 2003번 수들의 합 2 파이썬 :투 포인터 문제

 

구간의 부분합을 이용하는 문제 

Two Pointers 는 1차원 배열에서 두 개의 포인터를 조작하여 원하는 결과를 얻는 알고리즘입니다.

 

Two Pointers 의 조건은  배열의 원소가 자연수여야한다는 것 입니다.

자연수이기 때문에 end를 증가시키면 부분합이 증가하고 start를 증가시키면 부분합이 감소하는 것을 보장할 수 있지만 음수가 섞여있다는 이를 보장할 수 없으므로 Two Pointers를 사용할 수 없습니다.

여기서 두 개의 포인터를 사용하여 기존의 방식보다 시간을 개선할 수 있습니다.

start, end라는 두 개의 포인터를 사용합니다 .start는 부분배열의 앞 쪽을 가르키는 인덱스이고, end는 부분배열의 뒤 쪽을 가르키는 인덱스입니다.

https://ssungkang.tistory.com/entry/Algorithm-Two-Pointers-%ED%88%AC-%ED%8F%AC%EC%9D%B8%ED%84%B0

• 부분합 배열의 합 < 구해야하는 값

  end를 오른쪽으로 한 칸 이동하여 부분합 배열의 크기를 증가시킵니다.

• 부분합 배열의 합 >= 구해야하는 값

  start를 오른쪽으로 한 칸 이동하여 부분합 배열의 크기를 감소시킵니다.

 

---

문제

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

출력

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

 

n,m = map(int, input().split())
A=list(map(int, input().split()))
start=0
answer=0
end=0
while start <=end and end<=len(A):
    summ = sum(A[start:end])
    if summ==m:
        answer+=1
    if summ<=m:
        end+=1
        continue
    elif summ>m and start<end:
        start+=1
        continue
    else:
        start+=1
        end+=1
print(answer)

이 문제는 ssungkang.tistory.com/entry/Algorithm-Two-Pointers-%ED%88%AC-%ED%8F%AC%EC%9D%B8%ED%84%B0 이 블로그에서 보고 푼 문제 입니다. 

 

 

ssungkang.tistory.com/entry/Algorithm-Two-Pointers-%ED%88%AC-%ED%8F%AC%EC%9D%B8%ED%84%B0