[BOJ/백준] 2003번 - 수들의 합 2 Python

투 포인터(Two Pointers) : 두 지점을 통해 구간의 부분합 도출

 

- 시작점과 끝점(왼쪽 포인트와 오른쪽 포인터) 두 지점을 기준으로 하는 문제 풀이 전략.

 

 

각각의 포인터를 옮겨, 구간을 형성한다.

 

---

 

대표 문제 : 백준 2003번: 수들의 합 2

문제 링크 : www.acmicpc.net/problem/2003

---

 

 

접근법 

---

1. 슬라이싱을 통한 구간 선정

• 리스트[left:right]

2. 구간 부분합

• 구간의 합 < Target(M) : 오른쪽 포인터 → 이동 / 합을 늘리기 위함
• 구간의 합 > Target(M) : 왼쪽 포인터 → 이동 / 합계 줄이기 위함
• 구간의 합 = Target(M) : 카운트 증가,  오른쪽 포인터 → 이동

---

변수명

• N = 수열의 갯수, M = Target
• nums = 입력 수열
• left, right = 초기 포인터(배열의 인덱스)
• cnt = 카운트
• sum_nums = 구간( left ~ right )
• total = 구간의 부분합

 

CODE

---

N, M = map(int, input().split())
nums = list(map(int, input().split()))

left, right = 0, 1
cnt = 0
while right<=N and left<=right:

    sum_nums = nums[left:right]
    total = sum(sum_nums)

    if total == M:
        cnt += 1

        right += 1

    elif total < M:
        right += 1

    else:
        left += 1

print(cnt)