[백준] 2003. 수들의 합 2 / python 파이썬 / 투포인터, 구간합

🔍 투포인터(Two Pointers)

리스트에 순차적으로 접근해야 할 때 start point와 end point의 위치를 기록하면서 해결하는 방법

출처 : https://www.youtube.com/watch?v=rI8NRQsAS_s

 

🔍 구간 합(Prefix Sum)

◾  부분 합 : 0~k 까지의 합
◾  구간 합 : i~j 까지의 합

출처 : https://www.youtube.com/watch?v=rI8NRQsAS_s

N = 5
lst = [10, 20, 30, 40, 50]

# Prefix Sum 배열 계산
tmp = 0
prefix_sum = [0]
for num in lst:
	tmp += num
    prefix_sum.append(tmp)
    
# 구간 합 계산
left = 3
right = 4
print(prefix_sum[right] - prefix_sum[left-1])

 

---

boj 2003 코드

def sol(N, M, a):
    s, e = 0, 0
    subsum = a[0]
    cnt = 0
    while True:
        if subsum < M:  # 작으면 end point +1
            e += 1
            if e >= N:  # 인덱스 범위 주의
                break
            subsum += a[e]
        elif subsum == M:  # 같으면 cnt +1
            cnt += 1
            subsum -= a[s]
            s += 1
        else:  # 크면 start point +1
            subsum -= a[s]
            s += 1
    return cnt


N, M = map(int, input().split())
a = list(map(int, input().split()))
print(sol(N, M, a))