O(n log n) 이분 탐색 기법

누적 합 배열을 활용하여 각 시작 인덱스별로 X, Y, Z 합 구간의 종료 지점을 전처리합니다. 이진 탐색을 통해 정확히 X, Y, Z에 해당하는 부분 합의 끝 위치를 계산한 후, 연속된 세 구간이 조건을 만족하는지 O(n) 시간에 검증합니다.

#include <iostream>
#include <vector>
#include <climits>
using namespace std;
typedef long long ll;

int main() {
    ll num, targetX, targetY, targetZ;
    cin >> num >> targetX >> targetY >> targetZ;
    vector<ll> prefix(num + 1, 0);
    vector<ll> endX(num + 1, LONG_MAX);
    vector<ll> endY(num + 1, LONG_MAX);
    vector<ll> endZ(num + 1, LONG_MAX);

    for (int idx = 1; idx <= num; idx++) {
        ll val;
        cin >> val;
        prefix[idx] = prefix[idx - 1] + val;
    }

    for (int start = 1; start <= num; start++) {
        int low = start, high = num;
        while (low <= high) {
            int mid = (low + high) / 2;
            ll current = prefix[mid] - prefix[start - 1];
            if (current < targetX) low = mid + 1;
            else if (current > targetX) high = mid - 1;
            else {
                endX[start] = mid;
                break;
            }
        }
    }

    // Y, Z 대상 동일 이분 탐색 로직
    for (int start = 1; start <= num; start++) { 
        /* Y에 대한 탐색 코드 */ 
    }
    for (int start = 1; start <= num; start++) { 
        /* Z에 대한 탐색 코드 */ 
    }

    for (int i = 1; i <= num; i++) {
        if (endX[i] == LONG_MAX || endX[i] >= num) continue;
        int nextStart = endX[i] + 1;
        if (endY[nextStart] == LONG_MAX || endY[nextStart] >= num) continue;
        if (endZ[endY[nextStart] + 1] != LONG_MAX) {
            cout << "Yes";
            return 0;
        }
    }
    cout << "No";
    return 0;
}

O(n) 투 포인터 최적화

단일 패스로 각 시작점에 대한 종료 지점을 계산합니다. 포인터를 이동시키며 현재 구간 합이 목표값보다 작을 때만 우측으로 진행합니다. 모든 포인터가 총 n번만 이동하므로 선형 시간 복잡도를 보장합니다.

#include <iostream>
#include <vector>
#include <climits>
using namespace std;
typedef long long ll;

int main() {
    ll num, targetX, targetY, targetZ;
    cin >> num >> targetX >> targetY >> targetZ;
    vector<ll> prefix(num + 1, 0);
    vector<ll> endX(num + 1, LONG_MAX);
    vector<ll> endY(num + 1, LONG_MAX);
    vector<ll> endZ(num + 1, LONG_MAX);

    for (int idx = 1; idx <= num; idx++) {
        ll val;
        cin >> val;
        prefix[idx] = prefix[idx - 1] + val;
    }

    int ptrX = 1;
    for (int i = 1; i <= num; i++) {
        while (ptrX <= num && prefix[ptrX] - prefix[i - 1] < targetX) 
            ptrX++;
        if (prefix[ptrX] - prefix[i - 1] == targetX) 
            endX[i] = ptrX;
    }

    // Y, Z 대상 동일 포인터 로직
    int ptrY = 1;
    for (int i = 1; i <= num; i++) { 
        /* Y에 대한 포인터 처리 */ 
    }
    int ptrZ = 1;
    for (int i = 1; i <= num; i++) { 
        /* Z에 대한 포인터 처리 */ 
    }

    for (int i = 1; i <= num; i++) {
        if (endX[i] == LONG_MAX || endX[i] >= num) continue;
        int next = endX[i] + 1;
        if (endY[next] == LONG_MAX || endY[next] >= num) continue;
        if (endZ[endY[next] + 1] != LONG_MAX) {
            cout << "Yes";
            return 0;
        }
    }
    cout << "No";
    return 0;
}