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

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

2003번: 수들의 합 2

 

내 코드

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

cnt =0
left, right =0,1
while right <= n and left <= right:
    prefix_sum = sum(num[left:right])
    if prefix_sum == m:
        cnt +=1
        right +=1
    elif prefix_sum < m:
        right +=1
    elif prefix_sum > m:
        left +=1 
print(cnt)

 

코드 리뷰

슬라이딩 윈도우 알고리즘을 어제 학습하면서, 투 포인트도 비슷하다고 알게 되었다. 알고리즘의 이름 자체는 어려워보이지만, 막상 풀어보면 이것만큼 간단한 알고리즘은 없는 것 같다.

투 포인터

투 포인터는 슬라이딩 윈도우와 마찬가지로 부분 합을 구하는 알고리즘 중 하나이다.

이러한 배열이 있을 때, left 와 right를 직접 설정하면서 부분 합을 만들어내는 알고리즘이다.

처음에는 left와 right가 처음 원소를 가리키도록 한다.

그리고 right를 한 칸 더 옆으로 이동하면서 수가 일치하는지 확인한다.

만약 내가 5라는 수를 만들고 싶은데 [1,2,3]이 되면 커져서 5라는 숫자가 나오지 않을 수 있다.

이런 경우에는 left를 또 한 칸 옮겨서 구간 안의 수 합을 조금 줄이는 것이다.

만약 찾고 싶은 수를 찾아냈다면 카운트하면서 right 를 하나 더 높이면 된다.

구간 안의 합이 크면 left를 한 칸 더, 합이 작으면 right를 한 칸 더 움직인다.