[백준 2015] 수들의 합 4

www.acmicpc.net/problem/2015

2015번: 수들의 합 4

누적합과 구간합을 알아야 하는 문제이다.

가끔 보이는 유형인데 볼 때마다 못 푼다...ㅠㅠㅠ

 

eazymean.tistory.com/43

[알고리즘] Prefix Sum 구간 합/누적 합 알고리즘

 

누적합은 인덱스 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;
}