[백준] 11508 2+1 세일 JAVA

혅·2024년 3월 22일

1일1백준 -Java-

목록 보기

45/60

문제

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팩의 유제품을 구입하려고 합니다. 재현이를 도와 최소비용으로 유제품을 구입할 수 있도록 도와주세요!

입력

첫 번째 줄에는 유제품의 수 N (1 ≤ N ≤ 100,000)이 주어집니다.

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

출력

재현이가 N개의 유제품을 모두 살 때 필요한 최소비용을 출력합니다. 정답은 2^31-1보다 작거나 같다.

예제 입력

4
3
2
3
2

예제 출력

내가 했던 풀이 방법

가격을 내림차순으로 정렬한다.
가격 list의 index가 i%3==2일 때를 제외하고 모두 sum에 더해준다.
-> 가장 비싼 것부터 3쌍을 지어주면 된다. 예를 들어 [1, 2, 3, 4, 5, 6, 7]일 때 [7, 6, 5] / [4, 3, 2] / [1]로 구매하는 게 제일 저렴하다. (최대한 비싼 것들을 계산하지 않도록 해준다고 생각하면 됨)
-> i%3==2는 제외하는 이유는 내림차순으로 정렬되어있기 때문에 무료로 구매할 수 있는 유제품은 3,6,9,12...번째 유제품이고, list는 0부터 시작하기 때문에 index로 따지면 2,5,8,11이기 때문

코드

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Collections;

public class Main {
    public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());

        ArrayList<Integer> price = new ArrayList<>();
        for(int i=0; i<N; i++) {
            price.add(Integer.parseInt(br.readLine()));
        }

        Collections.sort(price);
        Collections.reverse(price);
        int sum = 0;
        for(int i=0; i<price.size(); i++) {
            if(i%3==2) continue;
            sum += price.get(i);
        }

        System.out.print(sum);
    } 
}