[Algorithm]Baekjoon 2015번 :: 수들의 합 4

https://www.acmicpc.net/problem/2015

 

 

#include <iostream>
#include <string>
#include <map>
#include <vector>
#include <algorithm>
#include <math.h>
#include <queue>
#include <functional>
#include <sstream>
#include <memory.h>
#include <deque>
#include <set>
#include <unordered_set>
#include <thread>
#include <atomic>
 
using namespace std;
 
 
int n, k, num;
 
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> n >> k;
 
    long long answer = 0;
    map<int, long long> count;
    int sum[200001] = { 0 };
    
    count[0] = 1;
 
    for (int i = 1; i <= n; ++i)
    {
        cin >> num;
 
        sum[i] = sum[i - 1] + num; // i번째 까지의 누적합 저장.
        answer += count[sum[i] - k];
        ++count[sum[i]];
    }
 
    cout << answer;
}
 
 

 

 

특정값 k를 만족하는 구간의 개수들을 구하는 문제이다.

문제에서 주어지는 배열의 값들이 양의 정수이면 투포인터로 쉽게 구할 수 있지만, 이 문제에는 음수가 섞여있다.

그래서 다른 방법을 생각해봐야 한다.

 

특정값 k가 무엇인지를 생각해본다.

k를 만족하는 i부터 시작해서 j로 끝나는 구간의 누적값을 sum(i,j)라 가정했을 때, k는 다음과 같다.

 

k = sum[j] - sum[i];    // j는 i보다 크거나 같다.

 

이걸 k의 개수관점으로 바꾸면 다음과 같다.

 

k의 개수 +=   (  sum[j] - sum[i] == k일 때, 'sum[i]를 만족하는 구간의 개수'  )

 

 

예를 들어 k가 20, 현재 인덱스까지의 누적합을 100이라 생각해보자.

그러면 우리는 누적값 80을 만족하는 인덱스의 개수를 구해서 카운팅해줘야 한다.

특정값을 만족하는 인덱스는 여러개가 있을 수 있다. 정수값들이 뒤죽박죽 섞여있기 때문이다.

즉 sum[1]이 80일 수도있고, sum[3]이 80일 수도 있다. 이 때 80을 만족하는 인덱스가 1,3 두개이기 때문에 이 두개를 카운팅해줘야 한다.

 

왜냐하면 sum[현재인덱스] - sum[1] or sum[3] == k 이기 때문이다.

 

그래서 처음부터 누적값을 map에다가 카운팅해주면서 진행해준다.

어차피 k값은 고정이니, 현재까지의 누적값에서 k를 빼준 값을 만족하는 누적값개수를 구하면 되는데, 이건 map에다가 계속 카운팅해왔으니 그대로 정답에다가 카운팅해주면 된다