[🥈3 / 백준 2003 / 파이썬] 수들의 합 2

 

2003번: 수들의 합 2

 

문제

N개의 수로 된 수열 A[1], A[2], …, A[N] 이 있다. 이 수열의 i번째 수부터 j번째 수까지의 합 A[i] + A[i+1] + … + A[j-1] + A[j]가 M이 되는 경우의 수를 구하는 프로그램을 작성하시오.

입력

첫째 줄에 N(1 ≤ N ≤ 10,000), M(1 ≤ M ≤ 300,000,000)이 주어진다. 다음 줄에는 A[1], A[2], …, A[N]이 공백으로 분리되어 주어진다. 각각의 A[x]는 30,000을 넘지 않는 자연수이다.

출력

첫째 줄에 경우의 수를 출력한다.

 

예제 입력 1  4 2 1 1 1 1	예제 출력 1  3
예제 입력 2  10 5 1 2 3 4 2 5 3 1 1 2	예제 출력 2  3

 

풀이

 

투 포인터는 배열에서 연속된 원소의 합이 특정 값과 일치하는지 계속하여 구할 때에 쓰이는 알고리즘이다.

i번째부터 j번째까지의 합이 M과 일치하는 경우가 얼마인지 계속해서 구해야 하는 이 문제가 

투 포인터의 대표격인 문제라고 할 수 있겠다.

 

구한 부분 수열의 합이 M보다 작은 경우 j를 증가, M보다 크거나 같다면  i를 증가한다.

그리고 부분수열의 합이 M과 같다면 카운트해준다.

만약, j가 n보다 커졌다면 배열에서 가능한 조합을 모두 훑은 것이므로 순회를 종료한다.

 

예제 2로 확인해보자.

 

 

i, j는 위와 같이 초기값 0으로 선언되어 맨 처음 원소인 1을 가르키고 있다.

이는 M에 해당하는 5보다 작으니 j를 늘려 더 많은 원소를 포함하게끔 해주자.

 

 

여전히 부분수열의 합이 5보다 작다. j를 더 증가시킨다.

 

부분수열의 합이 6으로, 5보다 크다. i를 증가시켜 원소의 수를 덜어내도록 하자.

 

부분수열의 합이 5로, M과 같다. 카운트해주도록 하자.

구했으니 끝이 아니라 다음 원소도 계속하여 탐색해야 하므로 j를 증가시켜준다.

 

이후론 위 과정의 반복이다.

 

이렇게 배열을 두 포인터로 순회하며 값을 검사하므로 시간복잡도는 O(2N), 즉 O(N)에 해당한다.

A[i:j+1] 을 sum으로 구하는 방식은 부분수열의 합을 구하기 위해 원소를 계속하여 훑게 되므로

약 O(N²)의 시간복잡도를 가지게 될 것이다. 부분수열을 직접 구해 합을 구하는 것이 아니라,

i와 j를 증가시키며 그 원소값을 다른 변수에 직접 가감하는 것이다. 헷갈리지 않도록 주의하도록 하자.

 

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

i,j,cnt,total = 0,0,0,0
while(True):
    if total >= m:
        total -= a[i]
        i += 1
    elif j == n:
        break
    else:
        total += a[j]
        j += 1
        
    if total == m:
        cnt += 1
    
print(cnt)