본문 바로가기
알고리즘 문제풀이/백준

[백준 2015] 수들의 합 4

by m2162003 2021. 1. 1.

www.acmicpc.net/problem/2015

 

2015번: 수들의 합 4

첫째 줄에 정수 N과 K가 주어진다. (1 ≤ N ≤ 200,000, |K| ≤ 2,000,000,000) N과 K 사이에는 빈칸이 하나 있다. 둘째 줄에는 배열 A를 이루는 N개의 정수가 빈 칸을 사이에 두고 A[1], A[2], ..., A[N]의 순서로

www.acmicpc.net

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

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

 

eazymean.tistory.com/43

 

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

prefix sum이란 구간 합을 의미한다. 예를 들어, int arr[5] = {10,20,30,40,50}; prefix sum은 prefix[i] = prefix[i-1] + arr[i]일 것이다. int prefix[5]; prefix[0] = arr[0]; for(int i=1; i 언제 쓰는가? 당..

eazymean.tistory.com

 

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

댓글