BOJ 2015 수들의 합 4

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

2015번: 수들의 합 4

 

 

map을 참신하게 활용하는 문제였습니다. 누적합은 $O(N)$에 구할 수 있습니다. 모든 부분합을 구하려고 하면 $O(N^{2})$으로 당연히 시간초과입니다.

 

 

 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int N, K, arr[200001], curSum;
ll ans;
map<int, int> m;

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

    m[0]++;
    
    cin >> N >> K;

    for(int i=1; i<=N; i++) cin >> arr[i];

    for(int i=1; i<=N; i++){
        curSum += arr[i];
        ans += (ll)m[curSum-K];
        m[curSum]++;
    }

    cout << ans;

}

 

 

정답 코드를 보면, 매번 $i$번째 원소까지의 누적합을 구하면서 key가 누적합인 map을 증가시키고 있습니다.

 

map에 저장된 각 누적합의 개수는 $1 \sim i$번째 원소까지의 배열중 부분합이 $K$인 것들의 개수를 구할때 요긴하게 사용됩니다. $1 \sim i$번째 원소의 누적합이 curSum일 때, 앞선 누적합 중 그 값이 curSum-K인 것들의 개수를 보면됩니다.

$(curSum-K)+curSum=K$이기 때문입니다.