[백준] 5545 최고의 피자 - Greedy / Java

• 문제 링크

5545번: 최고의 피자

 

• 풀이 과정

먼저 토핑을 선택하지 않은 경우의 1원당 열량 값, c / a 를 최대값으로 지정한다.

이 후 각 토핑의 열량 값을 입력받고, 이를 정렬해 큰 값부터 확인한다.

 

새로 토핑을 추가했을 때마다 1원 당 열량 값을 구하고, 이 값이 현재 최대 값과 같거나 크다면 갱신하고,

작다면 반복문을 탈출해 현재 최대값을 정답으로 출력한다.

 

• 풀이 코드

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.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        StringTokenizer st;

        int n = Integer.parseInt(br.readLine());

        st = new StringTokenizer(br.readLine());
        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(br.readLine());

        int[] arr = new int[n];
        for (int i = 0; i < n; i++)
            arr[i] = Integer.parseInt(br.readLine());

        Arrays.sort(arr);

        int cal = c, cost = a, max = c / a;
        while (n-- > 0) {
            cal += arr[n];
            cost += b;

            if (cal / cost >= max)
                max = cal / cost;
            else
                break;
        }

        bw.write(String.valueOf(max));
        bw.flush();
    }

}