[백준 2015번] 수들의 합 4 (C++)

문제링크 : https://www.acmicpc.net/problem/2015

2015번: 수들의 합 4

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int N, K, n, sum[200001];
ll result;
map<int, ll> m; //부분합, 카운팅

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);

    cin >> N >> K;
    
    for(int i=1; i<=N; i++) 
    {
        cin >> n;
        sum[i] = sum[i-1] + n; //누적합

        if(sum[i]==K) result++;
        result += m[sum[i]-K]; //부분합 갯수 체크
        m[sum[i]]++; //부분합 저장
    }

    cout << result;    
}

 

간단하게 누적합을 구하고 시작한다.

해당 누적합을 가지고 응용하여 부분합을 구해야 한다.

이를 위해서 일단 해당 문제에서 구하고자하는 K는 다음과 같은 식으로 표현해준다.

sum[i] - sum[j-1] = K
(1~i까지의 합) - (1~j-1까지의 합) = K (j~i까지의 합[부분합])

-> sum[i]-K = sum[j-1]

 

그리고 map을 이용하여 부분합을 Key로, 카운팅한 숫자를 Value로 저장한다.

따라서 부분합의 총 갯수를 담는 result에 현재 범위에 대한 부분합의 갯수인 m[sum[i]-K]를 저장하게 된다.

현재 sum[i]는 i가 1증가하게 되면 부분합이 되므로, 해당 부분합의 갯수로 카운팅해준다. ([sum[i]]++)

 

이 경우에 문제가 하나 있는데 바로 현재 누적합인 sum[i]가 K와 같은 경우이다.

앞서 구한 방식은 부분합인 sum[j~i]이므로 위의 경우를 인식하지 못한다.

따라서 sum[i]==K인 경우만 예외처리로 바로 result의 갯수를 증가시키도록 해주었다.