문제설명

각 구슬의 무게를 나타내는 weights 배열이다. weights[i]는 i번째 구슬의 무게를 나타낸다.구슬을 나눌 가방의 수 k입니다.
구슬을 다음 규칙에 따라 k개의 가방으로 나눠야 한다.

어떤 가방도 비어있지 않아야 한다. 만약 i번째 구슬과 j번째 구슬이 같은 가방에 있다면, i와 j 사이의 모든 구슬도 같은 가방에 있어야 한다.
i에서 j까지의 구슬이 포함된 가방의 비용은 weights[i] + weights[j]이다.
각 분배의 점수는 모든 k개의 가방의 비용 합입니다. 목표는 구슬을 분배했을 때 얻을 수 있는 최대 점수와 최소 점수의 차이를 찾는 것이다.

코드 설명

1.쌍 무게 합 계산
인접한 각 구슬 쌍의 무게 합을 저장하는 pair_weights 배열을 만든다.
예를 들어, weights가 [1, 3, 5, 1]이라면, pair_weights는 [1+3, 3+5, 5+1]이 되어 [4, 8, 6]이 되는 것이다.

2.쌍 무게 합 정렬
pair_weights 배열을 정렬하여 가장 작은 합과 가장 큰 합을 쉽게 찾을 수 있게 한다.
ex) [4, 8, 6] -> [4, 6, 8]이 되는 것.

3.최대 및 최소 점수 차이 계산
최대 점수는 가장 큰 k-1개의 쌍 무게 합을 선택하여 얻고, 최소 점수는 가장 작은 k-1개의 쌍 무게 합을 선택하여 얻습니다.
k-1번 반복하면서, 남아 있는 가장 작은 쌍 무게 합을 남아 있는 가장 큰 쌍 무게 합에서 빼준다.

4.차이 반환
최대 점수와 최소 점수의 차이를 answer에 저장하고 반환한다.

어려웠던 점

최대 및 최소 점수 차이를 계산하는 부분이 이해가 잘 가지 않았다.
문제에서 주어진 예제는 k-1=1이었기 때문에 더 짱구를 돌리면서 이해해보자.

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

예시

예를 들어, weights = [1, 3, 5, 1, 4, 2, 6]이고, k = 4라고 가정정해보자. 그러면 k-1 = 3, pair_weights는 [4, 8, 6, 5, 6, 8]이고 이 배열을 정렬하면 [4, 5, 6, 6, 8, 8]이 된다.

i = 0일 때:

answer += pair_weights[7 - 2 - 0] - pair_weights[0]
answer += pair_weights[5] - pair_weights[0]
answer += 8 - 4 = 4
따라서 answer = 4

i = 1일 때:

answer += pair_weights[7 - 2 - 1] - pair_weights[1]
answer += pair_weights[4] - pair_weights[1]
answer += 8 - 5 = 3
따라서 answer = 4 + 3 = 7

i = 2일 때:

answer += pair_weights[7 - 2 - 2] - pair_weights[2]
answer += pair_weights[3] - pair_weights[2]
answer += 6 - 6 = 0
따라서 answer = 7 + 0 = 7
최종적으로 answer는 7이 된다.

이 과정에서:

가장 큰 k-1개의 쌍 무게 합은 8, 8, 6이었고,
가장 작은 k-1개의 쌍 무게 합은 4, 5, 6이었다.
이 둘의 합 차이가 바로 최대 점수와 최소 점수의 차이라는 것이다.

코드

import heapq

class Solution(object):
    def putMarbles(self, weights, k):
        n = len(weights)
        pair_weights = [0] * (n - 1)
        for i in range(n - 1):
            pair_weights[i] = weights[i] + weights[i + 1]
        pair_weights.sort()
        answer = 0
        for i in range(k - 1):
            answer += pair_weights[n - 2 - i] - pair_weights[i]
        return answer