[Java][자바][백준][5545번] 최고의 피자

문제 설명

상근이는 근처 피자 가게에서 매일 저녁으로 피자를 배달해 먹는다. 주머니 사정이 얇아진 상근이는 이번 달부터는 "최고의 피자"를 구매하려고 한다. 최고의 피자란, 피자 가게에서 주문할 수 있는 피자 중 1원당 열량이 가장 높은 피자를 말한다. 최고의 피자는 여러 종류가 있을 수도 있다.

이 피자 가게는 토핑 N개에서 여러 종류를 선택해서 주문할 수 있다. 같은 종류의 토핑을 2개 이상 선택할 수는 없다. 또, 토핑을 전혀 선택하지 않을 수도 있다.

선택한 토핑은 도우 위에 올라간다. 도우의 가격은 A원이고, 토핑의 가격은 모두 B원이다. 피자의 가격은 도우와 토핑의 가격의 합계가 된다. 즉, 토핑을 k종류 (0 ≤ k ≤ N) 선택했다면, 피자의 가격은 A + B*k원이 된다. 피자의 열량은 도우와 토핑의 열량의 합이다.

도우의 가격, 토핑의 가격, 그리고 도우와 각 토핑의 열량 값이 주어졌을 때, 최고의 피자의 1원 당 열량을 구하는 프로그램을 작성하시오.

입력

첫째 줄에 토핑의 종류의 수 N(1 ≤ N ≤ 100)이 주어진다. 둘째 줄에는 도우의 가격 A와 토핑의 가격 B가 주어진다. (1 ≤ A, B ≤ 1000) 셋째 줄에는 도우의 열량 C가 주어진다. (1 ≤ C ≤ 10000) 다음 줄부터 N개 줄에는 각 토핑의 열량 Di가 한 줄에 하나씩 주어진다. (1 ≤ Di ≤ 10000)

출력

첫째 줄에 최고의 피자의 1원 당 열량을 출력한다. 소수점 이하는 버리고 정수 값으로 출력한다.

 

생각

그리디 알고리즘이다. 열량이 높은 토핑부터 추가하여 1원당 열량이 낮아지는 순간을 찾는데 욕심을 부리면서 문제를 해결한다.

 

토핑의 가격이 모두 일정하므로 당연히 열랑이 높은 토핑부터 추가하는게 1원 당 열량이 높아지는 방법이다. 

맨 처음 도우만 사용했을 때의 1원 당 열랑을 구하고 가장 열량이 높은 토핑을 추가하면서 1원 당 열량을 구하여 낮아지는 때를 확인하고 낮아진다면 바로 그 전의 열량이 최대가 될 것이다. (토핑을 열량이 높은 순부터 추가하므로 1원당 열량이 낮아진다면 그 후에는 계속 더 낮아질 것이다.)

 

코드

import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.StringTokenizer;
 
public class Main {
 
    public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int N = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine());
        int[] money = new int[2];
        
        //money[0] = 도우의 가격, money[1] = 각 토핑의 가격이 된다.
        for(int i=0; i<2; i++) {
            money[i] = Integer.parseInt(st.nextToken());
        }
        
        int kcal_dou = Integer.parseInt(br.readLine());
        
        int[] kcal_top = new int[N];
        
        for(int i=0; i<N; i++) {
            st = new StringTokenizer(br.readLine());
            kcal_top[i] = Integer.parseInt(st.nextToken());
        }
        //맨 처음 도우만 사용했을 때의 열량
        int total_price = money[0];
        int kcal = kcal_dou;
        int price_per_kcal = kcal/total_price;
        
        int new_total_price = money[0];
        int new_kcal = kcal_dou;
        int new_price_per_kcal = new_kcal/new_total_price;
        
        //토핑이 열량이 높은 순서부터 추가하기위해 정렬을 한다.
        Arrays.sort(kcal_top);
        
        for(int i=0; i<N; i++) {
            //새로운 토핑을 추가한 new_price_per_kcal을 구해서 현재의 1원당 열량과 차이를 비교한다.
            new_total_price += money[1];
            new_kcal += kcal_top[kcal_top.length-1-i];
            new_price_per_kcal = new_kcal/new_total_price;
            
            if(new_price_per_kcal >= price_per_kcal) {
                price_per_kcal = new_price_per_kcal;
                kcal = new_kcal;
                total_price = new_total_price;
            } else {
                break;
            }
        }
        
        System.out.println(price_per_kcal);
        
    }
 
}