백준 2003 수 들의 합2
부분합 알고리즘 풀이
#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;
}