5545번 : 최고의 피자

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

5545번: 최고의 피자

 

 

문제

 

 

코드

import java.io.*;
import java.util.*;

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));
        StringBuilder sb = new StringBuilder();
        int n = Integer.parseInt(br.readLine());
        StringTokenizer st = new StringTokenizer(br.readLine(), " ");
        int a = Integer.parseInt(st.nextToken());
        int b = Integer.parseInt(st.nextToken());
        int c = Integer.parseInt(br.readLine());

        Integer[] cal = new Integer[n];
        long sum[] = new long[n];
        for(int i=0;i<n;i++) cal[i]=Integer.parseInt(br.readLine());
        Arrays.sort(cal, Collections.reverseOrder());
        for(int i=0;i<n;i++) {
            if(i==0) sum[i]=cal[i]+c;
            else sum[i]+=sum[i-1]+cal[i];
        }

        long max=c/a; //토핑 안 올렸을 때, 1원당 열량
        int price=a;
        for(int i=0;i<n;i++) {
            price+=b;
            if(sum[i]/price>max) {
                max=sum[i]/price;
            }
        }

        bw.write(max+""); bw.flush();
    }
}

 

 

해결방법

입력받은 토핑을 내림차순 정렬 해준 뒤 토핑을 한 개씩 추가하면 토핑 개수 당 1원당 열량의 최댓값을 구할 수 있다. 고로,

입력받은 토핑을 내림차순 정렬 해준 뒤 토핑을 한 개씩 추가할 때마다 1원당 열량을 계산하여 가장 큰 값을 출력하였다.

1원당 열량을 계산할 땐, 시간초과가 날 것 같아서 미리 누적합을 배열에 저장해두었다.

 

도우 가격: 12
토핑 가격: 2

도우 열량: 200
토핑1 열량: 50
토핑2 열량: 300
토핑3 열량: 100
토핑: 300, 100, 50

k=0일 때, 가격: 12 , 열량: 200, 1원당 열량: 35
k=1일 때, 가격: 12 + 2 =14, 열량: 500, 1원당 열량: 35
k=2일 때, 가격: 12 + 4 =16, 열량: 600, 1원당 열량: 37
k=3일 때, 가격: 18, 열량: 650, 1원당 열량: 36