[백준 2003] 수들의 합
1. 요약
N개의 수로된 수열 A[1], A[2], ..., A[N]
이 있을 때, i
번째 수부터 j
번째 수까지의 합, A[i] + A[i+1] + A[i+2] + .. + A[j]
가 M이 되는 경우의 수를 구하는 문제
2. 아이디어
투 포인터를 이용하여 해결했다.
배열 A의 인덱스를 가리키는 start 포인터, end 포인터를 두고 start 포인터 가리키는 인덱스 <= end 포인터가 가리키는 인덱스를 유지하면서 start 포인터가 가리키는 배열 A값부터 end 포인터가 가리키는 배열 A값까지 더한다.
만약 결과가 같으면 카운트를 하고 M보다 작으면 end 포인터를 다음 위치로 이동한다.(i.e. 더한 결과가 M보다 작게 나왔기 때문에, end 포인터를 다음위치로 이동함으로써 향후 더한 결과를 이전 결과보다 크게 만들 수 있다.)
반대로 더한결과가 M보다 크면 start 포인터를 다음 위치로 이동한다. 따라서 향후 더해서 나오는 결과는 이전에 나왔던 결과보다 작을 것이다.
위의 과정을 end 포인터가 가리키는 인덱스가 N이 될 때까지 위의 과정을 수행한다.
3. 코드
import sys
n, m = map(int, sys.stdin.readline().rsplit())
arr = list(map(int, sys.stdin.readline().rsplit()))
sp, ep = 0, 0
answer = 0
while ep < n:
total = sum(arr[sp:ep+1])
if total == m:
answer += 1
ep += 1
elif sp == ep or total < m: ep += 1
else: sp += 1
print(answer)
Author And Source
이 문제에 관하여([백준 2003] 수들의 합), 우리는 이곳에서 더 많은 자료를 발견하고 링크를 클릭하여 보았다 https://velog.io/@study-dev347/백준-2003-수들의-합저자 귀속: 원작자 정보가 원작자 URL에 포함되어 있으며 저작권은 원작자 소유입니다.
우수한 개발자 콘텐츠 발견에 전념 (Collection and Share based on the CC Protocol.)