백준 2015: 수들의 합 4 [C/C++]

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

2015번: 수들의 합 4

#include <iostream>
#include <map>
#define fastio() ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
using namespace std;
long long n, k, cnt, lis[202020], acc[202020];
map<long long, long long> m;
int main() {
    fastio();
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> lis[i];
    for (int i = 1; i <= n; i++) acc[i] = acc[i - 1] + lis[i];
    for (int i = 1; i <= n; i++) {
        if (acc[i] == k) cnt++;
        if (m.find(acc[i] - k) != m.end()) cnt += m[acc[i] - k];
        if (m.find(acc[i]) != m.end()) m[acc[i]]++;
        else m.insert({acc[i], 1});
    }
    cout << cnt;
    return 0;
}
 

걸린 시간 : 00:24:36

 

풀이

1. 누적 합을 구한다.

 

2. 누적 합을 사용하여 부분 합을 구한다.

#include <iostream>
#define fastio() ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
using namespace std;
int n, k, cnt, lis[202020], acc[202020];
int main() {
    fastio();
    cin >> n >> k;
    for (int i = 1; i <= n; i++) cin >> lis[i];
    for (int i = 1; i <= n; i++) acc[i] = acc[i - 1] + lis[i];
    for (int i = 0; i <= n; i++) for (int j = i + 1; j <= n; j++) if (acc[j] - acc[i] == k) cnt++; 
    cout << cnt;
    return 0;
}
 

O(n^2)로 시간초과가 납니다.

 

 

2.  map을 사용한다.

앞에 누적 합이 얼마이며, 몇 개나 있는 지를 map으로 저장하면, 최종 O(nlogn)이 됩니다.