[Java] 백준 풀기 5545 - 최고의 피자

자바 백준 5545번

실버 3

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

5545번: 최고의 피자

 

 

 

 

 

문제 보기

분류: 그리디 알고리즘, 정렬

 

 

 

 

 

문제 풀기

도우의 1원당 열량을 초기값으로 지정한다. 그 후 토핑을 오름차순 정렬하여 열량이 높은 것부터 하나씩 합하면서 단위 열량을 매번 구하면서 최대값을 업데이트 저장한다.

 

 

 

 

 

코드 보기

import java.util.Arrays;
import java.util.Scanner;

class Pizza {
    private int toppingsCount;  // 토핑의 개수
    private int doughPrice;  // 도우의 가격
    private int toppingPrice;  // 토핑의 가격
    private int doughCalories;  // 도우의 열량
    private int[] toppingsCalories;  // 각 토핑의 열량
    
    // Constructor로 클래스 초기화
    public Pizza(int toppingsCount, int doughPrice, int toppingPrice, int doughCalories, int[] toppingsCalories) {
        this.toppingsCount = toppingsCount;
        this.doughPrice = doughPrice;
        this.toppingPrice = toppingPrice;
        this.doughCalories = doughCalories;
        this.toppingsCalories = toppingsCalories;
    }
    
    // 최고의 피자의 1원 당 열량 계산
    public int calculateMaxCaloriesPerPrice() {
        Arrays.sort(toppingsCalories);  // 토핑 열량을 오름차순으로 정렬
        
        int maxCaloriesPerPrice = doughCalories / doughPrice;  // 초기 도우 1원당 열량
        
        for (int i = toppingsCount - 1; i >= 0; i--) {
            int totalPrice = doughPrice + (toppingPrice * (toppingsCount - i));  // 토핑 i개를 선택한 가격
            int totalCalories = doughCalories + Arrays.stream(Arrays.copyOfRange(toppingsCalories, i, toppingsCount)).sum();  // 토핑 i개를 선택한 열량
            
            int caloriesPerPrice = totalCalories / totalPrice;  // i개의 토핑을 선택한 경우의 1원당 열량
            
            if (caloriesPerPrice > maxCaloriesPerPrice) {
                maxCaloriesPerPrice = caloriesPerPrice;  // 더 높은 1원당 열량으로 업데이트
            }
        }
        
        return maxCaloriesPerPrice;  // 최고의 피자의 1원 당 열량 반환
    }
}

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        
        int N = sc.nextInt();  // 토핑의 개수
        int A = sc.nextInt();  // 도우의 가격
        int B = sc.nextInt();  // 토핑의 가격
        int C = sc.nextInt();  // 도우의 열량
        
        int[] toppingsCalories = new int[N];
        for (int i = 0; i < N; i++) {
            toppingsCalories[i] = sc.nextInt();  // 각 토핑의 열량 입력
        }
        
        // Pizza 클래스를 생성하여 최고의 피자의 1원 당 열량 계산
        Pizza pizza = new Pizza(N, A, B, C, toppingsCalories);
        int result = pizza.calculateMaxCaloriesPerPrice();
        
        // 결과 출력
        System.out.println(result);
    }
}