누적합과 구간합을 알아야 하는 문제이다.
가끔 보이는 유형인데 볼 때마다 못 푼다...ㅠㅠㅠ
누적합은 인덱스 i까지의 배열 누적합을 의미하고
구간 합은 인덱스 i와 j 사이의 합을 의미한다.
누적합을 구하면 구간합은 쉽게 구하는데 i까지의 합 - j까지의 합이다.
이 문제에서도 마찬가지!! 구간합이 k가 되는 경우의 수를 구한다.
구간합을 구할 때 브루트포스를 사용하면 tle가 발생한다...따라서 psum[i] = psum[i-1] + tmp를 사용하도록 하자.
누적합을 구했다면
1. i까지의 누적합이 k인 경우
2. i와 j사이의 구간합이 k인 경우 두 가지가 있을 것이다.
2번같은 경우엔 psum[i] - psum[j] = k 식을 변형해서 psum[i]-k인 psum[j]의 수를 찾는다.
마지막엔 현재 구간합의 경우의 수를 맵에 더한다.
#include <stdio.h>
#include <map>
using namespace std;
int n, k;
map<int, long long> m;
int psum[200001];
int main(void)
{
scanf("%d%d", &n, &k);
for (int i = 1; i <= n; i++)
{
int tmp;
scanf("%d", &tmp);
psum[i] = psum[i - 1] + tmp;
}
long long ans = 0;
for (int i = 1; i <= n; i++)
{
if (psum[i] == k)
{
ans++;
}
ans += m[psum[i] - k];
m[psum[i]]++;
}
printf("%lld\n", ans);
return 0;
}
'알고리즘 문제풀이 > 백준' 카테고리의 다른 글
[백준 1026] 보물 (0) | 2021.01.03 |
---|---|
[백준 14588] Line Friends (Small) (0) | 2021.01.02 |
[백준 6118] 숨바꼭질 (0) | 2021.01.01 |
[백준 2262] 토너먼트 만들기 (0) | 2020.12.31 |
[백준 20310] 타노스 (0) | 2020.12.31 |
댓글