백준 11508 자바 - 2+1 세일 (BOJ 11508 JAVA)

문제 : boj11508

 

1. 어떻게 최소 비용을 만들 수 있을까?

  어차피 중복해서 물건을 구매할 수 없고, 모든 물건을 구매해야 하므로 N개의 물건에 대해 'N/3(내림)'개의 물건만을 2+1 세일로 가격을 빼낼 수 있다. 이걸 변경할 방법이 없으므로, 결국 최대한 비싼 물건을 세일로 빼내는 것이 최소 비용을 만들 수 있는 방법이다.

 

  이 때 특정 3개의 문제를 골랐을 때 이 중 가장 싼 물건의 가격이 빠지는 것이고, 이 '가장 싼 물건'이 최대한 비싼 물건일수록 이득이므로 결국 비싼 물건들부터 고르는 것 말고는 최소 비용을 만들 수 있는 방법이 없다. 즉, 문제 설명에서 나온 7개의 유제품 '10, 9, 4, 2, 6, 4, 3'을 봐보자. 문제에서는 위의 표처럼 그룹지었지만, 세일로 빠지는 가격을 늘리기 위해서는 아래의 표처럼 그룹지어야 한다. 이 경우 '9'만큼이나 세일받을 수 있다.

 

2. 로직

  결국 입력으로 들어온 모든 유제품의 가격을 내림차순으로 정렬한 후, 3개씩 짝지어서 그 중 가장 싼 가격은 무시하면 된다.

 

A. 내림차순 정렬

B. 큰 가격부터 낮은 가격으로 순회하면서 가격들을 더한다. 이 때 3의 배수번째(?)에 있는 수는 합계에 더하지 않는다.

 

 

 

코드 : github

import java.io.DataInputStream;
import java.io.IOException;
import java.util.ArrayList;
import java.util.Collections;

public class Main extends FastInput {
    private void solution() throws Exception {
        int n = nextInt();
        ArrayList<Integer> arr = new ArrayList<>(n);
        while (n-->0) arr.add(nextInt());
        Collections.sort(arr, Collections.reverseOrder());
        int sum = 0;
        for(int i = 0; i < arr.size(); i++) {
            if ((i+1)%3!=0)
                sum+=arr.get(i);
        }
        System.out.println(sum);
    }

    public static void main(String[] args) throws Exception {
        initFI();
        new Main().solution();
    }
}

class FastInput {
    private static final int DEFAULT_BUFFER_SIZE = 1 << 16;
    private static DataInputStream inputStream;
    private static byte[] buffer;
    private static int curIdx, maxIdx;

    protected static void initFI() {
        inputStream = new DataInputStream(System.in);
        buffer = new byte[DEFAULT_BUFFER_SIZE];
        curIdx = maxIdx = 0;
    }

    protected static int nextInt() throws IOException {
        int ret = 0;
        byte c = read();
        while (c <= ' ') c = read();
        do {
            ret = ret * 10 + c - '0';
        } while ((c = read()) >= '0' && c <= '9');
        return ret;
    }

    private static byte read() throws IOException {
        if (curIdx == maxIdx) {
            maxIdx = inputStream.read(buffer, curIdx = 0, DEFAULT_BUFFER_SIZE);
            if (maxIdx == -1) buffer[0] = -1;
        }
        return buffer[curIdx++];
    }
}