✂️ 초보자 친화 가이드 'Divide an Array Into Subarrays With Minimum Cost I' - 문제 3010 (C++, Python, JavaScript)

Source: Dev.to

Problem Summary

주어진 것:

• 길이가 n인 정수 배열 nums.
• 서브배열의 비용은 해당 서브배열 첫 번째 원소의 값으로 정의한다.

목표:

• 배열을 정확히 세 개의 연속된 서브배열로 나눈다.
• 세 서브배열 첫 번째 원소들의 합, 즉 총 비용을 최소화한다.

Intuition

서브배열은 연속이어야 하므로 원래 배열의 첫 번째 원소 nums[0]는 언제나 첫 번째 서브배열의 첫 번째 원소가 된다. 따라서 이 값은 반드시 총 비용에 포함된다.

합을 최소화하려면 남은 원소들(nums[1:]) 중에서 두 번째와 세 번째 서브배열의 시작점을 선택해야 한다. 최적의 선택은 그 접미사에서 가장 작은 두 값을 고르는 것이며, 이 값들이 각각 두 번째와 세 번째 서브배열의 첫 번째 원소가 된다.

Walkthrough: Understanding the Examples

Example 1

nums = [1, 2, 3, 12]

• 첫 번째 원소: 1
• 남은 원소: [2, 3, 12]
• 가장 작은 두 값: 2와 3
• 최소 총 비용: 1 + 2 + 3 = 6

Example 2

nums = [10, 3, 1, 1]

• 첫 번째 원소: 10
• 남은 원소: [3, 1, 1]
• 가장 작은 두 값: 1과 1
• 최소 총 비용: 10 + 1 + 1 = 12

Code Blocks

C++

class Solution {
public:
    int minimumCost(vector& nums) {
        // The maximum possible value based on constraints
        int min1 = 51;
        int min2 = 51;

        // Start from index 1 because nums[0] is always included
        for (int i = 1; i  // (loop logic omitted in original)
    }
};

Python

# nums[0] is always the start of the first subarray
first_val = nums[0]

# Get the rest of the array and sort to find the two smallest elements
remaining = nums[1:]
remaining.sort()

# Sum the first element and the two smallest from the rest
return first_val + remaining[0] + remaining[1]

JavaScript

/**
 * @param {number[]} nums
 * @return {number}
 */
var minimumCost = function(nums) {
    const firstVal = nums[0];

    // Extract everything after the first element
    let remaining = nums.slice(1);

    // Sort numerically in ascending order
    remaining.sort((a, b) => a - b);

    // The result is the sum of the first element and the two smallest remaining
    return firstVal + remaining[0] + remaining[1];
};

Key Takeaways

• Fixed Constraint: nums[0]가 항상 비용에 포함된다는 점을 인식하면 문제는 추가로 두 원소를 선택하는 것으로 단순화된다.
• Greedy Selection: 남은 배열에서 가장 작은 두 값을 고르면 최소 합을 보장한다.
• Efficiency: 두 최소값을 한 번의 순회로 찾으면 O(n) 시간에 해결할 수 있고, 정렬을 사용하면 O(n log n) 시간이 든다. 주어진 제약조건에서는 두 방법 모두 충분히 빠르다.

Final Thoughts

이 문제는 처음엔 복잡해 보이는 구분 작업이 실제 비용 정의에 집중하면 얼마나 단순해질 수 있는지를 보여준다. 서브배열의 첫 번째 원소만이 의미가 있다는 사실을 관찰함으로써 문제를 간단한 탐욕적 선택으로 바꿀 수 있다—이는 로드 밸런서에서 진입 지연 시간을 최소화하는 등 실제 최적화 시나리오에서도 자주 등장하는 접근법이다.