2023.07.08 Today's Challenge

fabichoi 2023. 7. 8. 23:45

https://leetcode.com/problems/put-marbles-in-bags/

Put Marbles in Bags - LeetCode

Can you solve this real interview question? 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 accord

leetcode.com

오랫만에 풀어봄

class Solution:
    def putMarbles(self, weights: List[int], k: int) -> int:
        n = len(weights)
        pw = [0] * (n - 1)
        for i in range(n-1):
            pw[i] = weights[i] + weights[i+1]
        pw.sort()

        answer = 0
        for i in range(k-1):
            answer += pw[n-2-i] - pw[i]
        
        return answer