99클럽 코테 스터디 7일차 TIL: [LeetCode] 2551. Put Marbles in Bags

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

 

혼자 고민하다가 백트래킹으로 풀었는데 시간 초과 + 오답이 났다. 그래서 다른 사람들 풀이를 봤는데 이해하지 못하다가 겨우 이해하고 다시 풀었다. 

 

특별한 알고리즘은 아닌 거 같고 문제를 이해하고 답이 나오는 과정을 이해하면 해결방법을 떠올릴 수 있다.

• score는 각 가방의 cost를 모두 더한 값이다.
• score를 구할 때 weights 배열의 첫 번째와 마지막 값은 무조건 포함된다. 따라서 두 개의 값은 고려할 필요가 없다. 
• 첫 번째와 마지막 값을 제외하면 score에 들어가는 값은 경계선에 있는 값들이다.
  • 만약 0, 1, 2, 3, 4번 인덱스를 가진 weights를 2개의 가방에 나눠 담는다고 가정하자.
  • 그리고 0~1번 인덱스까지 한 가방에, 2~4번 인덱스까지 한 가방에 넣는다고 가정하자.
  • 그러면 score는 첫 번째와 마지막인 0, 4를 제외하고 1과 2를 더한 3이 된다.
• 따라서 각 경계선에 있는 값들을 pairSum이라는 배열에 저장한다.
• 그리고 pairSum에서 k - 1개를 골라 더한다.
• 그런데 최솟값과 최댓값을 구해야 한다. 따라서 이때 최솟값은 pairSum에서 작은 수부터 k - 1개를 고르면 되고, 최댓값은 pairSum에서 큰 수부터 k - 1개를 고르면 된다.
• 따라서 pairSum을 정렬한 후 k - 1개를 고른다.

알고리즘부터 무작정 떠올리기 보다는 문제를 잘 이해하고 아이디어를 떠올리자.

import java.util.*;

class Solution {

    public long putMarbles(int[] weights, int k) {
        int n = weights.length;

        if (n == k) return 0;

        int[] pairSum = new int[n - 1];
        for (int i = 0; i < n - 1; i++) {
            pairSum[i] = weights[i] + weights[i + 1];
        }

        Arrays.sort(pairSum);

        // pairSum에서 k - 1개 구하기
        long min = 0;
        long max = 0;
        for (int i = 0; i < k - 1; i++) {
            min += pairSum[i]; // pairSum에서 작은 수부터 k - 1개 고르기
            max += pairSum[n - 2 - i]; // pairSum에서 큰 수부터 k - 1개 고르기
        }

        return max - min;
    }
}