백준 2143번 풀이

// https://www.acmicpc.net/problem/2143
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main(){
    long long t;
    cin >> t;

    int n, m;
    vector<int> a;
    vector<long long> as;
    vector<int> b;
    vector<long long> bs;

    cin >> n;
    long long temp_a = 0;
    for(int i = 0; i < n; i++){
        int temp;
        cin >> temp;
        temp_a += temp;
        a.push_back(temp);
        as.push_back(temp_a);
    }

    cin >> m;
    long long temp_b = 0;
    for(int i = 0; i < m; i++){
        int temp;
        cin >> temp;
        temp_b += temp;
        b.push_back(temp);
        bs.push_back(temp_b);
    }

    vector<long long> first;
    vector<long long> second;
    for(int i = 0; i < n; i++){
        first.push_back(as[i]); // i 까지의 누적
        for(int j = 0; j < i; j++){
            first.push_back(as[i] - as[j]);
        }
    }

    for(int i = 0; i < m; i++){
        second.push_back(bs[i]); // i 까지의 누적
        for(int j = 0; j < i; j++){
            second.push_back(bs[i] - bs[j]);
        }
    }

    sort(first.begin(), first.end());
    sort(second.begin(), second.end());

    long long cc = 0;
    long long l = 0;
    long long r = second.size()-1;

    while(true){
        if(l >= first.size() || r < 0){
            break;
        }

        long long result = first[l] + second[r];

        if(result == t){
            long long lc = 1;
            long long rc = 1;       
            while(l + lc < first.size() && first[l+lc] + second[r] == result){
                lc++;
            }

            while(r - rc >= 0 && first[l] + second[r-rc] == result){
                rc++;
            }

            cc += lc*rc;
            l = l + lc;
            r = r - rc;

        }else if(result < t){
            l++;
        }else if(result > t){
            r--;           
        }
    }


    cout << cc << "\n";
    return 0;
}

주어진 시간제한이 2초라 무식하게 풀었는데도 맞았다. 

 

기본적으로 1208번 문제랑 똑같다. 추가한건 부배열을 좀 편하게 구하려고 

1) a, b라는 각각의 값을 넣는 vector를 만들고

2)as, bs라는 a의 값을 순서대로 누적해서 저장한 vector를 만들고

3) 이 누적합과 각각의 합을 기준으로 first, second라는 부배열의 합을 모두 구한 배열을 만든 뒤

4) first는 앞에서부터 second는 뒤에서부터 합을 체크해서 갯수를 세주는 방식이다.