<Baekjoon> #2003 수학, 구현, Dynamic Programming_수들의 합2 c++

#2003 수들의 합

풀이 1
먼저 보고 바로 dp로 풀어야겠다고 생각했고
dp[i][j]=a[i] 부터 a[j] 까지의 합으로 설정했다.
(자꾸 dp, bfs, dfs문제 들을 풀다보니 이런 문제도 그런 알고리즘으로 풀어야겠다고 생각한다 ㅠㅠ)

e.g. n=10 m=5 a={1,2,3,4,2,5,3,1,1,2}
dp[i][i]인 경우는 모두 a[i]를 채워놓고 시작한다

그 다음부터는
dp[i][j]=dp[i][j-1]+a[j] 의 아이디어로 채워넣는다

이렇게 차례대로 다 채우면 이렇게 되고 이 중 m인 경우는 3개이다.

#include <iostream>
#include <vector>
#include <string.h>

using namespace std;
const int MAX = 10000;

int main() {
	int n, m;
	int cnt = 0;
	cin >> n>>m;
	vector<int> num(n);
	int dp[MAX][MAX];
	memset(dp, 0, sizeof(dp));
	for (int i = 0; i < n; i++) 
		cin >> num[i];

	for (int i = 0; i < n; i++){
		dp[i][i] = num[i];
        if (dp[i][i]==m) cnt++;
    }

	for (int i = n - 2; i >= 0; i--) {
		for (int j = i + 1; j < n; j++) {
			dp[i][j] = dp[i][j - 1] + num[j];
			if (dp[i][j] == m) cnt++;
		}
	}
	cout << cnt << endl;
	return 0;
}

당연히 엄청 비효율적인 코드에 메모리 초과가 났다
애초부터 dp를 쓸 필요도 없었고 수열의 합이 m인 개수를 구하는 것이므로 채우다가 m보다 큰 수가 나오면 더 이상 볼 필요도 없었다.

풀이2

• 수열 a가 있을 때, 합을 구하려는 시작 위치를 begin, 끝을 end로 두고 합을 구한다.
• 합이 m보다 작으면 계속 end를 늘려가며 더해준다
• 합이 m보다 커지면 이때까지 구한 합에서 a[begin]을 빼주고 시작 위치를 begin+1로 변경해주어 다시 합을 구한다.
• 코드에서 주의할 점은 수열의 크기를 원래 크기보다 1보다 크게 했는데 while문 내부에서 end를 늘릴 때 ++end로 늘리기 때문에 원래 크기보다 1보다 크게 할당하지 않으면 런타임 에러가 난다.

#include <iostream>
#include <vector>
using namespace std;

int main() {
	int n, m;
	int cnt = 0;
	cin >> n >> m;
	vector<int>num(n+1);

	for (int i = 0; i < n; i++)
		cin >> num[i];

	int sum = num[0];
	int start = 0; int  end = 0;

	while (start <= end && end<n) {
		if (sum < m)
			sum += num[++end];
		else if (sum == m) {
			cnt++;
			sum += num[++end];
		}
		else if (sum > m) {
			sum -= num[start++];
			if (start > end) {
				end = start;
				sum = num[start];
			}
		}
	}
	cout << cnt << endl;
	return 0;
}