[알고리즘] 백준 11508 - 2+1 세일

분류 : 그리디

1. 문제

https://www.acmicpc.net/problem/11508
KSG 편의점에서는 과일우유, 드링킹요구르트 등의 유제품을 '2+1 세일'하는 행사를 하고 있습니다. KSG 편의점에서 유제품 3개를 한 번에 산다면 그중에서 가장 싼 것은 무료로 지불하고 나머지 두 개의 제품 가격만 지불하면 됩니다. 한 번에 3개의 유제품을 사지 않는다면 할인 없이 정가를 지불해야 합니다.

예를 들어, 7개의 유제품이 있어서 각 제품의 가격이 10, 9, 4, 2, 6, 4, 3이고 재현이가 (10, 3, 2), (4, 6, 4), (9)로 총 3번에 걸쳐서 물건을 산다면 첫 번째 꾸러미에서는 13원을, 두 번째 꾸러미에서는 10원을, 세 번째 꾸러미에서는 9원을 지불해야 합니다.

재현이는 KSG 편의점에서 친구들과 같이 먹을 총 N팩의 유제품을 구입하려고 합니다. 재현이를 도와 최소비용으로 유제품을 구입할 수 있도록 도와주세요!

2. 입력

첫 번째 줄에는 유제품의 수 N (1 ≤ N ≤ 100,000)이 주어집니다.
두 번째 줄부터 N개의 줄에는 각 유제품의 가격 Ci (1 ≤ Ci ≤ 100,000)가 주어집니다.

3. 풀이

PriorityQueue를 쓰면 아주 간단하게 풀 수 있다.
유제품을 가격이 큰 순서대로 정렬한 후 3개씩 묶으면, 최소 가격을 지불하고 구입할 수 있다.
PriorityQueue에 유제품 가격을 넣고 3개씩 묶어서 빼면서 마지막 1개 가격을 카운트하지 않으면 된다.

4. 코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Comparator;
import java.util.PriorityQueue;

public class sale {
    public static void solution() throws IOException{
        BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));

        //전체 유제품 수
        int N = Integer.parseInt(bf.readLine());

        int answer = 0;

        //큰 순서대로 저장
        PriorityQueue<Integer> queue = new PriorityQueue<>(Comparator.reverseOrder());

        for(int i=0;i<N;i++){
            queue.offer(Integer.parseInt(bf.readLine()));
        }

        while(!queue.isEmpty()){
            //3개씩 빼줌
            for(int i=0;i<3;i++){
                //더이상 없으면 중지
                if(queue.isEmpty())
                    break;
                int tmp = queue.poll();
                if(i!=2){
                    answer += tmp;
                }


            }
        }

        System.out.println(answer);
    }

}