[C++][백준] 수들의 합 2(2003)

문제

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을 넘지 않는 자연수이다.

 

출력

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

 

풀이

자연수가 주어지고, 연속적인 합이 특정 조건을 만족해야 할 때 투포인터 알고리즘을 떠올릴 수 있습니다.

 

투포인터 알고리즘에서는 s, e 두개의 포인터가 사용되는데 

s는 부분합의 시작지점, e는 부분합의 끝 지점을 의미합니다. 

(저는 e가 가리키는 값은 포함하지 않기 때문에 s와 e가 동일한 경우 아무것도 포함하지 않은 부분집합이 됩니다.)

 

테스트 케이스 2번을 기반으로 그림을 그려보도록 하겠습니다.

10 5 1 2 3 4 2 5 3 1 1 2

 

e가 가리키는 값은 포함하지 않기 때문에 위 그림에서 부분합은 0이 됩니다.

이때 모든 수가 자연수이기 때문에 e가 증가하면 무조건 부분합이 증가한다는 것이 보장됩니다. 

e를 증가시켜줍니다.

 

 

부분합이 증가하였으나 우리는 부분합이 M(5)가 되는 경우의 수를 구해야하기때문에 e를 증가시킵니다.

 

이때 부분합이 M보다 커지게 됩니다.

우리는 부분합이 M(5)가 되는 경우의 수를 구해야 하는데 이미 부분합이 M(5)보다 큰 상황에서 e가 증가하면 무조건 부분합이 증가할 수 밖에 없습니다. 따라서 s가 가리키는 값을 제외하고 s를 증가합니다.

 

이때 부분합이 우리가 원하는 M(5)가 되었기 때문에 경우의 수를 하나 추가해줍니다.

우리는 부분합이 M(5)가 되는 경우의 수를 구해야 하는데 이미 부분합이 5인 상황에서 e가 증가하면 무조건 부분합이 증가할 수 밖에 없습니다. 따라서 s가 가리키는 값을 제외하고 s를 증가합니다.

 

 

동일한 과정을 e가 배열범위를 넘어서는 순간, 즉 e가 N보다 커질때까지 반복해줍니다.

 

 

전체코드는 아래와 같습니다.

#include <iostream>

using namespace std;

int N, M;
int arr[10010];

int main() {
	cin >> N >> M;

	int ans = 0;

	for (int i = 0; i < N; i++) {
		cin >> arr[i];
	}

	int s = 0, e = 0, tmp = 0;

	while (1) {
		if (tmp >= M) {
			tmp -= arr[s];
			s++;
		}
		else if (tmp < M) {
			tmp += arr[e];
			e++;
		}

		if (tmp == M) ans++;
		if (e > N) break;
	}

	cout << ans;

	return 0;
}