백준 No.5545 최고의 피자 - JAVA

 

 

문제

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

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

 

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

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

 

입력

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

3
12 2
200
50
300
100

 

제출할 때 70퍼를 넘어가는 순간부터 계속 틀렸다고 해서 코드 계속 고쳐봤는데 도저히 몰라서 답을 보니.. 토핑을 안 고를 수도 있던 것이었다..... 문제를 똑바로 봐야할 거 같다.

 

풀이

- 문제는 오름차순으로 토핑을 정렬한다. 정렬한 후에 해당 가장 큰 값부터 A+(B*k) 를 통해 가격을 구하는데 토핑이 하나일 경우부터 K번째까지 구해야한다. 결국 가장 큰 값일 때는 k가 1이다. 가장 작은 값일 경우는 k가 k일 것이다. 1~k

- 이렇게 구한 가격을 도우열량+토핑개수만큼더한값 을 나눠야한다. 여기서 토핑 개수만큼 더한 값은 k만큼이다. 결국 가장 큰 열량의 토핑은 k가 1이므로 도우열량+토핑1개(가장 큰 거)  일테고 k 가 2일 경우 도우열량+(토핑 가장큰 거 + 토핑 두번째 큰 거) 이런식으로 구해서 나눈다.

- 토핑을 안 고를 경우가 열량이 높을 수도 있다. 이런 경우는 계속해서 계산식을 대입 할 변수에 시작부터 도우열량을 도우 가격으로 나눈 값을 대입한다. 그리고 for문에서는 if문으로 if(토핑 안 고름 > 토핑 변화하는 값) 일 경우 break를 걸면 된다. 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;
import java.util.Comparator;
import java.util.StringTokenizer;

public class Main {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        int N = Integer.parseInt(br.readLine());    //토핑의 종류
        StringTokenizer st = new StringTokenizer(br.readLine());    //\A B
        int A = Integer.parseInt(st.nextToken());
        int B = Integer.parseInt(st.nextToken());

        int weightA = Integer.parseInt(br.readLine());
        Integer weightK[] = new Integer[N];

        for (int i = 0; i < N; i++) {
            weightK[i] = Integer.parseInt(br.readLine());
        };

        Arrays.sort(weightK, Comparator.reverseOrder());

        int res = 0;
        int price = 0;
        int result = weightA/A;
        int cal = weightA;
        for (int i = 0; i < N ; i++) {
            price = A + (B * (i+1)) ;
            cal += weightK[i];

             res = cal / price;
            if(result > res){break;}
             if(result < res){
                result = cal / price;
            }
        }
        System.out.println(result);
    }
}