[백준] 2003 수 들의 합2

백준 2003 수 들의 합2

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

부분합 알고리즘 풀이

#include <iostream>
using namespace std;

typedef unsigned long int ul;
const int MAXN = 10000 + 1;

int N;
ul M;
int A[MAXN];
ul psum[MAXN];

void getpsum() {
	psum[0] = 0;
	for (int i = 1; i <= N; ++i)
		psum[i] = psum[i - 1] + A[i];
	return;
}

ul getCnt() {
	ul ret = 0;
	for (int i = 1; i <= N; ++i)
		for (int j = i; j <= N; ++j)
			if (psum[j] - psum[i - 1] == M)
				++ret;
	return ret;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N >> M;
	for (int i = 1; i <= N; ++i)
		cin >> A[i];

	getpsum();
	cout << getCnt();
	return 0;
}

⚡투 포인터 알고리즘 풀이

• psum = A[start]부터 A[end - 1]까지의 부분 합

#include <iostream>
using namespace std;

typedef unsigned long int ul;
const int MAXN = 10000 + 1;

int N;
ul M;
int A[MAXN] = { 0 };

ul getCnt() {
	ul ret = 0;
	int start = 0;
	int end = 0;
	ul psum = 0;

	while (end <= N) {
		if (psum >= M)
			psum -= A[start++];
		else if (psum < M)
			psum += A[end++];

		if (psum == M)
			ret++;
	}

	return ret;
}

int main() {
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	cin >> N >> M;
	for (int i = 0; i < N; ++i)
		cin >> A[i];

	cout << getCnt();
	return 0;
}