(c++)백준 2003번: 수들의 합 2

www.acmicpc.net/problem/2003

2003번: 수들의 합 2

[풀이]

투포인터로 풀 수 있는 문제였다.

투포인터는 하나의 배열에 두 개의 포인터를 사용하는 알고리즘으로, 배열의 원소가 모두 자연수이므로 사용할 수 있었다. 

1. start와 end포인터를 0으로 초기화

2. 합이 M보다 작으면 end포인터를 이동시켜 값을 크게 해주기

3. M보다 크면 start포인터를 이동시켜 값을 작게 해주기

4. M과 같으면 count + 1, start포인터 이동시키기

#include <iostream>
using namespace std;

int N, M;
int A[10001];

int countM() {
	int cnt = 0;
	int startx = 0;
	int endx = 0;
	int sum = 0;
	while (endx <= N) {
		if (sum < M) {
			sum += A[endx];
			endx++;
		}
		if (sum >= M) {
			if (sum == M)
				cnt++;
			sum -= A[startx];
			startx++;
		}
	}
	return cnt;
}

int main() {
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}
	cout << countM() << '\n';
	return 0;
}

+ 투포인터 말고 dfs로도 풀 수 있었다. (투포인터 방법보다 시간복잡도가 더 큰 방법)(투포인터 : 4ms, dfs : 32ms)

//dfs조합으로 풀어보기
#include <iostream>
using namespace std;

int N, M;
int A[10001];
bool check[10001];
int cnt = 0;

void dfs(int x, int sum) {
	if (sum > M)
		return;
	if (sum == M) {
		cnt++;
		return;
	}
	if (x >= N)
		return;
	dfs(x + 1, sum + A[x]);
}

int main() {
	cin >> N >> M;
	for (int i = 0; i < N; i++) {
		cin >> A[i];
	}
	for (int i = 0; i < N; i++) {
		dfs(i, 0);
	}
	cout << cnt << '\n';
	return 0;
}