[백준/파이썬] 2003번: 수들의 합 2

문제

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

풀이

• 수열의 i번째 수부터 j번째 수까지의 합이 M이 되는 경우의 수 출력

투 포인터 알고리즘을 활용하는 문제

l,r: 배열의 왼쪽, 오른쪽 인덱스(0,1로 초기화)
cnt: 부분합이 m이 되는 수
total: l부터 r까지 부분합

1. total이 m과 같을 경우: 부분합이 m이 되는 순간이 존재하므로 cnt 증가, 다음 구간을 확인하기 위해 r 증가
2. total이 m보다 큰 경우: 부분합이 크므로 시작점을 오른쪽으로 옮기기 위해 l 증가
3. total이 m보다 작은 경우: 부분합이 부족하므로 끝점을 오른쪽으로 옮기기 위해 r 증가

while문 조건을 끝점(r)이 배열의 길이(n)보다 길어지거나 시작점(l)이 끝점을 넘어가면 종료하도록 설정하여 반복문이 종료되면 cnt를 리턴하도록 하였습니다.

코드

import sys
input = sys.stdin.readline

def func(n,m,a):
    l,r = 0,1
    cnt = 0

    while r <= n and l <= r:
        total = sum(a[l:r])
    
        if total == m:
            cnt += 1
            r += 1
        elif total > m:
            l += 1
        else:
            r += 1
        
    return cnt

if __name__ == "__main__":
    n,m = map(int,input().split())
    a = list(map(int,input().split()))
    print(func(n,m,a))