백준 2015 수들의 합 4

#include <iostream>
#include <map>

using namespace std;


int prefix[200001];


int main() {

    ios::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);


    int n, k, num;
    long long ans = 0;
    map<int, long long> m;      //m[i]=j: 누적합으로 i를 만들 수 있는 경우의 수=j


    cin >> n >> k;

    for (int i = 1; i <= n; i++) {
        cin >> num;
        prefix[i] = prefix[i - 1] + num;
        if (prefix[i] == k) ans++;

    }

    for (int i = 1; i <= n; i++) {
        ans += m[prefix[i] - k];
        m[prefix[i]]++;     //1~i의 누적합
    }



    cout << ans;





    return 0;
}

 

n을 20만까지 허용하므로 구간합을 모두 구하면 시간초과가 난다. 

따라서 누적합으로 숫자를 만드는 경우의 수를 저장하는 map을 사용하여 문제를 해결해야 한다.

 

우선 값을 입력받으면서 1~i번째의 구간합이 k이면 그 경우를 추가한다.

 

그 후 

k=arr[i]-arr[j-1]->arr[j-1]=arr[i]-k이므로 이를 성립시키는 j를 찾으면 된다.

예를 한번 들어보자.

 

4 0
2 -2 2 -2

 

위의 입력이 주어졌다.

 

i=1: 누적합에 2가 들어가고, k와 다르므로 넘어간다. 

       ans+=m[prefix[i]-k]에서 ans+=m[2-0]

       m[prefix[i]]++에서 m[2]++가 된다. 1~1번째의 구간합이다.

i=2: 누적합 prefix[2]=0이 되고, k와 같으므로 ans++(1)이 된다.

       ans+=m[prefix[i]-k]에서 ans+=m[0-0]=0

      m[prefix[i]]++에서 m[0]++(1)이 된다. 1~2번째의 구간합이다.

i=3: 누적합 prefix[3]=2가 되고, k와 다르므로 넘어간다.

       ans+=m[prefix[i]-k]에서 ans+=m[2-0]=m[2]=1

       즉, 인덱스 3 이전으로 구간합을 구하는 과정에서 구간합이 k임을 성립시키는 j가 존재하는 것이다.(2~3의 구간합)

      m[prefix[i]]++에서 m[2]++가 된다. 1-3번째의 구간합이다.

i=4: 누적합 prefix[4]=0이 되고, k와 같으므로 ans++(3)

       ans+=m[prefix[i]-k]에서 ans+=m[0-0]=m[0]=1->ans=4

       즉, 인덱스 4 이전으로 구간합을 구하는 과정에서 구간합이 k임을 성립시키는 j가 존재하는 것이다.(3~4의 구간합)

      m[prefix[i]]++에서 m[0]++가 된다. 1-4번째의 구간합이다.

 

위의 과정을 거쳐 4가 출력되는 것이다.

 

ps. 이해하는데 정말 오래 걸렸다. 나중에 다시 한 번 보자