[백준/2003] 수들의 합| 부분합과 누적합의 차이를 명확하게 | 투포인터

https://www.acmicpc.net/problem/2003

2003번: 수들의 합 2

알고리즘

누적합: psum[i] = psum[i-1] + li[i]로 피보나치처럼 누적해서 더함. 끝으로 갈수록 앞의 값들이 누적되어 값이 커짐

부분합: psum은 앞에서부터 차차 누적해서 더한다면 부분합은 i와 j까지의 합이다. psum[j]-psum[i-1]을 통해 구할 수도 있지만 이렇게 되면 이중 포문을 사용해야 하기 때문에 복잡도가 커진다. 따라서 이진탐색과 같이 두 개의 포인터를 사용하여 "구간합"을 구한다.

---

최종 코드

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

left, right = 0, 1
cnt = 0
    
while left <= right <= n:
    ans = sum(li[left:right])
    
    if ans < m : right += 1
    elif ans > m : left += 1
    else: cnt += 1; right += 1

print(cnt)

---

알게된 점

구간합, 누적합과 동시에 RMQ 알고리즘을 배워서 개념 자체가 헷갈렸다.ㅠㅠ 누적합 문제와 구간합 문제를 비교하면서 풀어보니 이해가 된다!! RMQ 알고리즘은 결국 구간합의 활용이라고 할 수 있겠다. 또 구간합과 누적합의 완전한 경계가 없는 이유 또한 느낌상으로 와닿았다. 굳이 말하자면 구간합은 누적합의 부분집합이다. 이제 각각의 차이를 깨달았으니 문제를 풀어나가면서 구현 방법을 익혀야겠다.