[백준] 2003 수들의 합2 (Python 파이썬)

www.acmicpc.net/problem/2003

2003번: 수들의 합 2

문제 설명

N개의 수열 A[1],A[2], ..., A[N]이 주어졌을 때, 수열의 부분 합이 M이 되는 경우의 수를 구하는 문제입니다.

즉, 중간중간 A[2]+A[3]+A[4] = M이라면 경우의 수가 하나 추가가 되는 문제입니다.

---

풀이 과정

전형적인 투포인터 문제입니다.

시작점과 끝점을 먼저 시작점에 놓습니다.

 

주어진 수들은 모두 자연수이기 때문에

현재 구간의 합이 M보다 작다면 현재 구간의 끝점을 늘려야 합니다.

 

반대로, 현재 구간의 합이 M보다 크다면 시작점을 늘려야 합니다.

 

같은 경우는 카운트를 하나 늘려주고, start가 end보다 앞에 있는 경우는 start를 한 칸 뒤로,

반대의 경우는 end를 한 칸 뒤로 늘려주어 start가 end뒤로 오지 않도록 유지해줍니다.

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

start = 0
end = 0
count = 0

while end < len(alist) and start < len(alist):
    if sum(alist[start:end+1]) < m:
        end += 1

    elif sum(alist[start:end+1]) == m:
        count += 1
        if start < end:
            start += 1
        else:
            end += 1

    else:
        start += 1

print(count)

 

https://github.com/HongEunho

전체 문제 & 코드는 위의 깃에 정리되어 있습니다.

팔로우 & 맞팔은 환영입니다 !