[BOJ] 두 배열의 합

두 배열의 합

TimeLimit	MemoryLimit	Condition	TAG
2s	64MB	-1,000,000,000 ≤ T ≤ 1,000,000,000 1 ≤ n ≤ 1,000 1 ≤ m ≤ 1,000	Sort, Binary Search, 누적합

진짜 정말 너무 아쉬웠다… 처음 논리에서 별로 벗어나진 않았는데 이상한 코드를 짠 것을 그대로 쓰다가 아예 갈엎으니 바로 ac를 맞았다. 진짜 미치겠다. 어쩌다가…

하튼 일단 문제는 누적합으로 조합을 쫘라락 중복되지 않도록 구하고, 이후에 정렬하고서 이분탐색으로 돌면서 그 슬라이싱된 값들을 빠르게 찾는 전략으로 진행했습니다.

정답 코드

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
using ll = long long;

ll t;
ll A[1'000'000];
ll B[1'000'000];

ll input(ll *current) {
    int n;
    cin >> n;
    vector<ll> arr(n);
    for (int i = 0; i < n; ++i) cin >> arr[i];
    int idx = 0;
    for (int i = 0; i < n; ++i) {
        ll sum = 0;
        for (int j = i; j < n; ++j) {
            sum += arr[j];
            current[idx++] = sum;
        }
    }
    return idx;
}

ll solution(ll n, ll m) {
    ll result = 0;
    sort(A, A + n);
    sort(B, B + m);

    for (int i = 0; i < n; ++i) {
        ll target = t - A[i];
        ll left = 0, right = m - 1;
        ll rl = -1, rr = -1;

        while (left <= right) {
            ll pivot = (right + left) / 2;
            if (B[pivot] >= target) {
                right = pivot - 1;
                if (B[pivot] == target) rl = pivot;
            } else  left = pivot + 1;
        }

        left = 0;
        right = m - 1;
        while (left <= right) {
            ll pivot = (right + left) / 2;
            if (B[pivot] <= target) {
                left = pivot + 1;
                if (B[pivot] == target) rr = pivot;
            } else right = pivot - 1;
        }

        if (rl != -1 && rr != -1) result += (rr - rl + 1);
    }

    return result;
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> t;
    ll n = input(A);
    ll m = input(B);

    cout << solution(n, m);

    return 0;
}