🛂 초보자 친화 가이드 'Divide an Array Into Subarrays With Minimum Cost II' - Problem 3013 (C++, Python, JavaScript)

Source: Dev.to

Source: …

Problem Overview

데이터를 최적의 구간으로 나누는 것은 컴퓨터 과학에서 고전적인 과제로, 특정 제약 조건과 효율성 사이의 균형을 요구합니다.
이 문제는 배열을 가장 저렴한 비용으로 분할하면서, 분할 지점들이 서로 거리 제한을 만족하도록 하는 방법을 찾는 것입니다. 슬라이딩 윈도우 기법과 정렬된 이동 데이터를 유지하기 위한 고급 자료구조를 결합하는 훌륭한 연습이 됩니다.

You are given

• 정수 배열 nums.
• 정수 k, 만들어야 할 부분 배열의 개수.
• 정수 dist, 두 번째 부분 배열과 마지막 부분 배열의 시작 인덱스 사이의 최대 거리 제한.

Goal

전체 비용을 최소화합니다. 여기서 부분 배열의 비용은 첫 번째 원소가 됩니다.
첫 번째 부분 배열은 항상 인덱스 0에서 시작하므로 nums[0]는 항상 비용에 포함됩니다.
우리는 배열의 나머지 부분에서 k‑1개의 시작 인덱스를 선택해 합을 최소화하고, dist 제약을 만족해야 합니다.

Formalisation

k개의 부분 배열 시작 인덱스를

[ p_1, p_2, \dots, p_k ]

라고 하겠습니다.

• p_1은 항상 0입니다.
• 1 … n‑1 범위에서 k‑1개의 인덱스를 선택합니다.
• 제약 조건

[ p_k - p_2 \le \text{dist} ]

은 두 번째부터 k번째까지 선택된 모든 인덱스가 크기 dist인 윈도우 안에 들어가야 함을 의미합니다.

이 dist 크기의 윈도우를 배열 전체에 슬라이드하면서, 그 윈도우 안에 있는 k‑1개의 가장 작은 원소들의 합을 빠르게 찾아야 합니다.
이를 효율적으로 수행하기 위해 **Binary Indexed Tree (Fenwick Tree)**와 coordinate compression을 사용합니다. 이 방법을 통해 숫자들을 “랭크”화하고, 이진 리프팅(binary lifting)을 이용해 로그 시간 안에 가장 작은 값들을 찾을 수 있습니다.

Example

nums = [1,3,2,6,4,2], k = 3, dist = 3

우리는 창에서 k‑1 = 2개의 인덱스를 선택해야 합니다.

• 창의 크기는 dist + 1 = 4입니다.

• 첫 번째 선택한 인덱스가 1이면, 마지막 인덱스는 최대 1 + dist = 4까지 가능합니다.

  인덱스 1 … 4를 보면: [3, 2, 6, 4].
  가장 작은 두 수는 2와 3입니다.
  비용 = nums[0] + 2 + 3 = 1 + 5 = 6.

• 첫 번째 선택한 인덱스가 2이면, 마지막 인덱스는 5까지 가능합니다.

  인덱스 2 … 5를 보면: [2, 6, 4, 2].
  가장 작은 두 수는 2와 2입니다.
  비용 = 1 + 2 + 2 = 5.

가능한 최소 비용은 5입니다.

참조 구현

C++ (GNU C++17)

#include <bits/stdc++.h>
using namespace std;

class Solution {
    int max_rank;
    vector<int> bit_count;
    vector<long long> bit_sum;
    vector<int> sorted_values;

    // Add / remove a value from the BIT
    void update(int idx, int count_delta, long long val_delta) {
        for (; idx <= max_rank; idx += idx & -idx) {
            bit_count[idx] += count_delta;
            bit_sum[idx]   += val_delta;
        }
    }

    // Query sum of smallest `target` elements
    long long query(int target) {
        int idx = 0;
        int cur_k = 0;
        long long cur_s = 0;
        for (int i = 1 << (31 - __builtin_clz(max_rank)); i; i >>= 1) {
            int next_idx = idx + i;
            if (next_idx <= max_rank && cur_k + bit_count[next_idx] < target) {
                idx   = next_idx;
                cur_k += bit_count[next_idx];
                cur_s += bit_sum[next_idx];
            }
        }
        // add the remaining part of the (target‑cur_k)‑th element
        return cur_s + 1LL * (target - cur_k) * sorted_values[idx];
    }

public:
    int minCost(vector<int>& nums, int k, int dist) {
        int n = nums.size();

        // coordinate compression
        sorted_values = nums;
        sort(sorted_values.begin(), sorted_values.end());
        sorted_values.erase(unique(sorted_values.begin(), sorted_values.end()), sorted_values.end());
        max_rank = sorted_values.size();

        bit_count.assign(max_rank + 1, 0);
        bit_sum.assign(max_rank + 1, 0);

        auto get_rank = [&](int val) {
            return lower_bound(sorted_values.begin(), sorted_values.end(), val) - sorted_values.begin() + 1;
        };

        int target_k = k - 1;                     // we need k‑1 additional starts

        // initialise the window (first `dist + 1` elements, but not beyond the array)
        for (int i = 1; i <= min(dist, n - 1); ++i) {
            update(get_rank(nums[i]), 1, nums[i]);
        }

        long long min_cost = nums[0] + query(target_k);

        // slide the window across the array
        for (int i = 2; i + dist < n; ++i) {
            // remove element leaving the window
            update(get_rank(nums[i - 1]), -1, -nums[i - 1]);
            // add new element entering the window
            update(get_rank(nums[i + dist]), 1, nums[i + dist]);

            long long cur = nums[0] + query(target_k);
            min_cost = min(min_cost, cur);
        }
        return (int)min_cost;
    }
};

Python

def minCost(nums, k, dist):
    n = len(nums)

    # ---- coordinate compression ----
    sorted_unique = sorted(set(nums))
    ranks = {val: i + 1 for i, val in enumerate(sorted_unique)}
    max_rank = len(sorted_unique)

    bit_count = [0] * (max_rank + 1)   # how many numbers of each rank
    bit_sum   = [0] * (max_rank + 1)   # sum of those numbers

    def update(rank: int, c_delta: int, v_delta: int) -> None:
        while rank <= max_rank:
            bit_count[rank] += c_delta
            bit_sum[rank]   += v_delta
            rank += rank & -rank

    def query(target: int) -> int:
        idx = 0
        cur_k = 0
        cur_s = 0
        i = max_rank.bit_length()
        while i >= 0:
            next_idx = idx + (1 << i)
            if next_idx <= max_rank and cur_k + bit_count[next_idx] < target:
                idx   = next_idx
                cur_k += bit_count[next_idx]
                cur_s += bit_sum[next_idx]
            i -= 1
        return cur_s + (target - cur_k) * sorted_unique[idx]

    target_k = k - 1

    # initialise the window (first `dist + 1` elements, but not beyond the array)
    for i in range(1, min(dist + 1, n)):
        update(ranks[nums[i]], 1, nums[i])

    min_cost = nums[0] + query(target_k)

    # slide the window across the array
    for i in range(2, n - target_k + 1):
        # remove the element that leaves the window
        update(ranks[nums[i - 1]], -1, -nums[i - 1])
        # add the new element entering the window
        update(ranks[nums[i + dist - 1]], 1, nums[i + dist - 1])

        cur = nums[0] + query(target_k)
        min_cost = min(min_cost, cur)

    return min_cost

Source: …

1])

        # add the new element that enters the window (if any)
        if i + dist < n:
            update(ranks[nums[i + dist]], 1, nums[i + dist])

        cur = nums[0] + query(target_k)
        min_cost = min(min_cost, cur)

    return min_cost

자바스크립트 (Node.js)

function minCost(nums, k, dist) {
    const n = nums.length;

    // ---- coordinate compression ----
    const sortedUnique = Array.from(new Set(nums)).sort((a, b) => a - b);
    const ranks = new Map();
    sortedUnique.forEach((val, i) => ranks.set(val, i + 1));
    const maxRank = sortedUnique.length;

    const bitCount = new Array(maxRank + 1).fill(0);
    const bitSum   = new Array(maxRank + 1).fill(0n); // use BigInt for safety

    const update = (rank, cDelta, vDelta) => {
        while (rank <= maxRank) {
            bitCount[rank] += cDelta;
            bitSum[rank]   += BigInt(vDelta);
            rank += rank & -rank;
        }
    };

    const query = (target) => {
        let idx = 0, curK = 0, curS = 0n;
        for (let i = Math.floor(Math.log2(maxRank)); i >= 0; i--) {
            const nextIdx = idx + (1 << i);
            if (nextIdx <= maxRank && curK + bitCount[nextIdx] < target) {
                idx   = nextIdx;
                curK += bitCount[nextIdx];
                curS += bitSum[nextIdx];
            }
        }
        const remaining = target - curK;
        return curS + BigInt(remaining) * BigInt(sortedUnique[idx]);
    };

    const targetK = k - 1;

    // initialise the window (first `dist + 1` elements, but not beyond the array)
    for (let i = 1; i <= Math.min(dist, n - 1); i++) {
        update(ranks.get(nums[i]), 1, nums[i]);
    }

    let minCost = BigInt(nums[0]) + query(targetK);

    // slide the window across the array
    for (let i = 2; i + dist < n; i++) {
        // remove element leaving the window
        update(ranks.get(nums[i - 1]), -1, -nums[i - 1]);
        // add new element entering the window
        update(ranks.get(nums[i + dist]), 1, nums[i + dist]);

        const cur = BigInt(nums[0]) + query(targetK);
        if (cur < minCost) minCost = cur;
    }

    return Number(minCost);
}

Key Techniques

Coordinate Compression

When the value range (up to 10^9 or larger) far exceeds the number of elements n, we map each distinct value to a compact rank. This lets us use the ranks as indices in arrays (e.g., Fenwick trees).

Dual Fenwick Tree

One BIT stores counts of elements, the other stores sums of their values. Together they enable fast “sum of the smallest K elements” queries.

Binary Lifting on BIT

Instead of a linear scan or a binary search over the BIT, we use binary lifting to locate the prefix where the cumulative count first reaches (or exceeds) K. This reduces the search to O(log maxRank).

Why This Matters

The problem is a classic example of handling streaming data with tight time constraints:

• In real‑world systems (e.g., high‑frequency trading platforms), you often need the “best K prices in the last T minutes.”

• A sliding window combined with an order‑statistic data structure (the dual BIT) provides the necessary efficiency.

• Although the problem appears daunting as a “Hard” challenge, breaking it down into:

  1. Window management, and
  2. Efficient rank‑based queries

  makes the solution both understandable and implementable.