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

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

2015번: 수들의 합 4

 

 

[ 문제풀이 ]

 

1. 배열의 1번부터 N번까지 수를 입력받으면서 누적합을 arr 배열에 저장하고, unordered_map<int, long long> um 자료구조에 누적합의 개수를 저장합니다.

 

2. ans에 um[ arr[ i ] - K ] 의 개수를 더해줍니다.

 

3. ans를 출력합니다.

 

[ 소스코드 ]

#include<iostream>
#include<unordered_map>
#define ll long long
 
using namespace std;
 
int N, K;
int arr[200001];
unordered_map<int, ll> um;
ll ans;
 
int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);
 
    cin >> N >> K;
 
    um[0] = 1;
 
    for (int i = 1; i <= N; i++) {
        cin >> arr[i];
        arr[i] += arr[i - 1];
 
        ans += um[arr[i] - K];
 
        um[arr[i]]++;
    }
 
    cout << ans;
}