[SWEA] 4050 재관이의 대량 할인

 

3개로 묶었을 때 그 중 가장 작은 옷값은 할인을 해준다

그럼 그리디로 생각해서 묶으면 된다

 

어차피 제일 큰건 할인 못받는다

3*k 번째로 큰 애들만 할인 받을 수 있다

 

편하게 pq에 값을 넣고 탐색해보자!

자바는 min heap 이므로 -를 붙여서 넣으면 최대힙으로 바꿀 수 있다

 

그리고 pq에서 하나씩 꺼내보며 만약 3*k 번째 옷이라면 값을 더하지 말자!

 

소스코드

import java.util.PriorityQueue;
import java.util.Scanner;
 
public class Solution {
 
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t= sc.nextInt();
         
        for(int tc=1;tc<=t;tc++) {
            int n = sc.nextInt();
            PriorityQueue<Integer> pq = new PriorityQueue<>();
            for(int i=0;i<n;i++) {
                int x = sc.nextInt();
                pq.add(-x);
            }
            int ans=0;
            while(!pq.isEmpty()) {
                int sum=0;
                for(int i=0;i<3;i++) {
                    if(pq.isEmpty()) break;
                    int now = -pq.poll();
                    if(i==2) break;
                    sum+=now;
                }
                ans+=sum;
            }
            System.out.println("#"+tc+" "+ans);
        }
         
    }
}