[LeetCode] 2551. Put Marbles in Bags

https://leetcode.com/problems/put-marbles-in-bags/description/?envType=daily-question&envId=2025-03-31

leetcode - Put Marbles in Bags

문제 유형: 그리디, 정렬, 구현

문제 난이도: Hard

 

문제

You have k bags. You are given a 0-indexed integer array weights where weights[i] is the weight of the ith marble. You are also given the integer k.

Divide the marbles into the k bags according to the following rules:

• No bag is empty.
• If the ith marble and jth marble are in a bag, then all marbles with an index between the ith and jth indices should also be in that same bag.
• If a bag consists of all the marbles with an index from i to j inclusively, then the cost of the bag is weights[i] + weights[j].

The score after distributing the marbles is the sum of the costs of all the k bags.

Return the difference between the maximum and minimum scores among marble distributions.

 

구슬 배열이 있습니다. 구슬을 k개의 가방에 담아야 합니다.

모든 가방에 구슬이 적어도 하나 들어가야 하며, 구간 i, j를 골라[i, ..., j]까지의 구슬을 모두 담아야 합니다.

가방의 cost는 weights[i] + weights[j]값입니다.

 

최대 cost들의 합에 최소 cost들의 합을 뺀 값을 구하시오.

 

풀이

영어로 보기: https://leetcode.com/problems/put-marbles-in-bags/solutions/6598110/simple-solution-sorting-c-go-by-fudoge-9iou/

 

k개의 서브어레이로 나눠야 하므로, k-1번의 분할을 시행해야 한다.

각각의 분할마다, weights[i], weights[i+1]의 값이 더해진다. 거기에 기본적으로 weights[0]과 weights[n-1]은 항상 포함이다.

즉, 인접한 두 쌍의 weights값의 합들 중에서 가장 큰 k-1개들의 합에 가장 작은 k-1개들의 합을 빼면 된다.

 

 

코드

C++

using ll = long long;
class Solution {
   public:
    ll putMarbles(vector<int>& weights, int k) {
        int n = weights.size();
        vector<ll> pairsums;
        for (int i = 0; i < n - 1; i++) {
            pairsums.emplace_back(weights[i] + weights[i + 1]);
        }
        sort(pairsums.begin(), pairsums.end());

        ll maxSum = 0, minSum = 0;
        for (int i = 0; i < k - 1; i++) {
            minSum += pairsums[i];
            maxSum += pairsums[n - 2 - i];
        }

        return maxSum - minSum;
    }
};

 

Go

func putMarbles(weights []int, k int) int64 {
	n := len(weights)

	maxSum := int64(0)
	minSum := int64(0)
	sums := make([]int64, n-1)
	for i := 0; i < n-1; i++ {
		sums[i] = int64(weights[i] + weights[i+1])
	}
	sort.Slice(sums, func(i, j int) bool {
		return sums[i] < sums[j]
	})

	for i := 0; i < k-1; i++ {
		minSum += sums[i]
		maxSum += sums[n-2-i]
	}

	return maxSum - minSum
}