1962. Remove Stones to Minimize the Total

문제

https://leetcode.com/problems/remove-stones-to-minimize-the-total/description/

풀이

class Solution {
    public int minStoneSum(int[] piles, int k) {
        PriorityQueue<Integer> heap = new PriorityQueue<>(Comparator.reverseOrder());
        int answer = 0;

        for(int n : piles) {
            heap.add(n);
        }

        for(int i = 0; i < k; i++) {
            int x = heap.poll();
            heap.add(x - (x/2));
        }

        for(int n : heap) {
            answer += n;
        }

        return answer;
    }
}

• piles를 하나 집어서 절반(내림)만큼 버리는걸 k번 반복
• k번 반복했을 때 가장 적은 수의 piles들이 남아야함
  • 이를 위해선 반복할 때마다 가장 높은 수의 piles를 버려야한다.
    => Heap 사용