백준 15720 - 카우버거 (자바 - 그리디)

https://www.acmicpc.net/problem/15720

15720번: 카우버거

 

* 문제 요약

카우버거에 세트 할인을 도입하고자 한다. 세트 메뉴는 버거 1개, 사이드 메뉴 1개, 음료 1개를 선택할 경우 각각의 제품에 대해서 10% 의 세트 할인을 적용하는 방식으로 진행된다.

가게의 POS 기에 세트 할인 프로그램을 직접 만든다고 할 때 해당 프로그램을 작성해보자.

 

* 입력

첫째 줄에는 주문한 버거의 갯수 B, 사이드 메뉴의 갯수 C, 음료의 갯수 D 가 공백을 사이에 두고 순서대로 주어진다.

(1 <= B, C, D <= 1,000)

둘째 줄에는 각 버거의 가격이 공백을 사이에 두고 주어진다.

셋째 줄에는 각 사이드 메뉴의 가격이 공백을 사이에 두고 주어진다.

넷째 줄에는 각 음료의 가격이 공백을 사이에 두고 주어진다.

각 메뉴의 가격은 100의 배수이며, 10,000 원을 넘지 않는다.

 

* 출력

첫째 줄에는 세트 할인이 적용되기 전 가격을 출력한다.

둘째 줄에는 세트 할인이 적용된 후의 최소 가격을 출력한다.

 

* 예제

 

* 해결 과정

세트 할인이 적용된 후 최소 가격을 구하려면 각 메뉴를 하나씩 묶어서 세트를 만들었을 때, 해당 세트의 가격이 가장 비싼 경우를 찾아야 한다.

그래야 10% 의 세트 할인을 적용할 때 가격이 가장 큰 폭으로 할인되어 최소 가격을 찾을 수 있기 때문이다.

 

세트 메뉴 갯수 판정의 기준은 버거, 사이드, 음료 중 가장 가짓수가 적은 메뉴의 갯수이다.

그렇기 때문에 메뉴 갯수 배열 count 를 오름차순 정렬해서 나온 첫번째 인덱스 값이 곧 만들어질 수 있는 세트 메뉴의 갯수에 해당된다.

그 값을 menuCount 변수에 저장해둔다.

 

이후 각 줄 마다 메뉴에 대한 가격을 버거, 사이드, 음료 배열에 각각 저장해준 다음 각 배열의 내용을 합산한 값을 모두 더해서 세트 할인이 적용되기 전 가격을 구해준다.

그 다음 세트 할인이 적용되었을 경우 최소 가격을 구해주기 위해 각 메뉴 배열을 내림차순으로 정렬해준 다음 앞서 구했던 menuCount 크기 만큼 매 반복마다 버거 + 사이드 + 음료 값을 합산해준 다음 0.9 를 곱해서 현재 세트 메뉴에 할인이 적용된 가격을 구해준다.

 

menuCount 만큼 세트 메뉴를 만들고 할인이 모두 적용되고 난 후, 세트 메뉴로 만들어지지 않은 나머지 버거, 사이드, 음료가 남아있을 경우 그 가격들 까지 모두 합산하여 전체 가격을 구해준다.

이렇게 해서 나온 가격이 곧 세트 할인이 적용되었을 경우 얻을 수 있는 최소 가격이 되는 것이다.

 

* 코드

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.IOException;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.Collections;

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

    private void solution() throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        String[] input = br.readLine().split(" ");
        int[] count = new int[input.length];
        for (int i = 0; i < input.length; i++) {
            count[i] = Integer.parseInt(input[i]);
        }
        Arrays.sort(count);
        int menuCount = count[0];

        Integer[] burger = new Integer[Integer.parseInt(input[0])];
        Integer[] side = new Integer[Integer.parseInt(input[1])];
        Integer[] drink = new Integer[Integer.parseInt(input[2])];

        input = br.readLine().split(" ");
        for (int i = 0; i < burger.length; i++) {
            burger[i] = Integer.parseInt(input[i]);
        }
        input = br.readLine().split(" ");
        for (int i = 0; i < side.length; i++) {
            side[i] = Integer.parseInt(input[i]);
        }

        input = br.readLine().split(" ");
        for (int i = 0; i < drink.length; i++) {
            drink[i] = Integer.parseInt(input[i]);
        }

        int before = Arrays.stream(burger).reduce(0, (a, b) -> a + b) +
                Arrays.stream(side).reduce(0, (a, b) -> a + b) +
                Arrays.stream(drink).reduce(0, (a, b) -> a + b);

        Arrays.sort(burger, Collections.reverseOrder());
        Arrays.sort(side, Collections.reverseOrder());
        Arrays.sort(drink, Collections.reverseOrder());

        int result = 0;
        int i = 0;
        for (; i < menuCount; i++) {
            int sum = (int) ((burger[i] + side[i] + drink[i]) * 0.9);
            result += sum;
        }
        int index = i;
        if (i < burger.length) {
            index = i;
            for (; index < burger.length; index++) {
                result += burger[index];
            }
        }
        if (i < side.length) {
            index = i;
            for (; index < side.length; index++) {
                result += side[index];
            }
        }
        if (i < drink.length) {
            index = i;
            for (; index < drink.length; index++) {
                result += drink[index];
            }
        }

        bw.write(before + "\n" + result + "\n");
        bw.flush();
        bw.close();
        br.close();
    }
}

 

최소 가격을 구하기 위해 각 메뉴를 내림차순 한 다음 세트 메뉴를 만들어서 세트 할인의 폭을 최대한 크게 만들었다.

조건에 맞는 답을 구하기 위해 내림차순 정렬을 통해 매 반복마다 최적의 경우를 찾았으므로 정렬 및 그리디 알고리즘 문제에 해당된다.