2551. Put Marbles in Bags

[zeikar]

Problem link

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

Problem Summary

가방 안의 돌들을 k 그룹으로 묶을 때 최소 합과 최대 합의 차이를 구하는 문제.

Solution

처음에는 DP 느낌이지만 수가 너무 많다.
정답은 그리디로 가면 된다.

뭔가 정렬 느낌이긴 했는데 잘 안돼서 에디토리얼 참고함.

사진은 에디토리얼에서 가져옴

일단 시작 돌과 마지막 돌은 무조건 포함해야 하니 제외하자. 그러면 k-1번 가방의 돌들을 나누는 문제가 된다. 여기서 나눌 때 더해지는 값은 잘린 부분의 양쪽 값. 이 2개의 돌의 값을 최소화 or 최대화 하면 정답이 된다.

Source Code

class Solution:
    def putMarbles(self, weights: List[int], k: int) -> int:
        pair_weights = []
        for i in range(1, len(weights)):
            pair_weights.append(weights[i - 1] + weights[i])

        pair_weights.sort()

        minans = 0
        for i in range(k - 1):
            minans += pair_weights[i]
        minans += weights[0] + weights[-1]
        
        maxans = 0
        for i in range(k - 1):
            maxans += pair_weights[len(pair_weights) - i - 1]
        maxans += weights[0] + weights[-1]

        return maxans - minans