2551. Put Marbles in Bags

문제

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.

• n개의 구슬을 백에 모두 담아야 합니다.
• k개의 백이 주어집니다.
• i < j 인 index i와 j에 대해 백에 넣으려면 i~j까지의 모든 구슬을 넣어야 합니다.
  • 즉 1, 3, 4 만 구슬에 넣을수는 없고 1, 2, 3, 4를 다 넣어야 가능하다는 뜻
• 다만 백의 값어치는 첫번째와 마지막 index의 무게만을 더합니다.
• k개의 백에 최대로 가능한 값어치의 합과 최소로 가능한 값어치의 합을 뺀 값을 리턴하시오

---

예시

weights = [1,3,5,1], k = 2

• 배열을 [1], [3, 5, 1]로 나누면, 각 부분 배열의 합은 각각 1과 9입니다. 여기에 1을 더하면 2와 10이 되고, 이들의 합은 12가 됩니다. 하지만 이 문제에서 제시된 계산 방식에 따르면 (1+1) + (3+5+1+1) = 2 + 10 = 12가 아닌 (1+1)+(3+1)=6입니다.
• 배열을 [1, 3], [5, 1]로 나누면, 각 부분 배열의 합은 각각 4와 6입니다. 여기에 1을 더하면 5와 7이 되고, 이들의 합은 12가 됩니다. 하지만 이 문제에서 제시된 계산 방식에 따르면 (1+3+1)+(5+1)=5+6=11이 아닌 (1+3+1) + (5+1) = 5 + 6 = 11입니다.
• 최소 점수를 만드는 배열 분할은 [1], [3, 5, 1]이며, 이 때의 점수는 (1+1) + (3+1) = 6입니다.
• 최대 점수를 만드는 배열 분할은 [1, 3], [5, 1]이며, 이 때의 점수는 (1+3+1) + (5+1) = 10입니다.
• 따라서 최대 점수와 최소 점수의 차이는 10 - 6 = 4입니다.

---

제한

• $1 <= k <= weights.length <= 10^5$
• $1 <= weights[i] <= 10^9$

---

풀이법

• 일단 구슬은 반드시 백 안에 들어가야 하기 때문에 단 한개의 백에 넣었다고 가정하면 최소는
  weights[0] + weights[-1] 이 될 것이다.
• 근데, 여기서 중간을 끊어서 ( i와 i+1 ) 두개의 백에 옮겨담으면 값은 weights[i] + weights[i + 1]만큼 늘 것이다.
• 또한 끊은 부분을 한번 더 끊는것은 불가능
• 그렇다면 weights[i] + weights[i + 1]을 미리 계산해서 정렬하고 k번만큼 더한걸 빼면 그만 아님?
• 어 그렇네?

class Solution:
    def putMarbles(self, weights: List[int], k: int) -> int:
        N, p = len(weights), []

        for i in range(N - 1):
            p.append(weights[i] + weights[i + 1])

        p.sort()

        ans = 0

        for i in range(k - 1):
            ans -= p[i]
            ans += p[-1-i]

        return ans