[ Baekjoon - 11/12 ] - 5545번: 최고의 피자

• 문제 링크 : https://www.acmicpc.net/problem/5545

5545번: 최고의 피자

 

• 소요 시간 : 39분 33초 (백준 확장프로그램 왜 이제서야 알았을까ㅠ)

최고의 피자

시간 제한메모리 제한제출정답맞힌 사람정답 비율

1 초

128 MB

2958

1172

1033

43.042%

문제

상근이는 근처 피자 가게에서 매일 저녁으로 피자를 배달해 먹는다. 주머니 사정이 얇아진 상근이는 이번 달부터는 "최고의 피자"를 구매하려고 한다. 최고의 피자란, 피자 가게에서 주문할 수 있는 피자 중 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 복사

3
12 2
200
50
300
100

예제 출력 1 복사

37

예제 입력 2 복사

4
20 3
900
300
100
400
1300

예제 출력 2 복사

100

 

1. 문제를 읽고 이해하기
   • 제한
     • 시간 : 1초
     • 메모리 : 128MB
   • 문제
     • N개의 토핑종류 [1, 100]
       도우가격 A, 토핑가격 B [1,1000]
       도우열량 C [1,10,000]
       각 토핑 열량 D[1, 10,000]
     • 최고의 피자란 1원당 열량이 가장 높은 피자를 일컫는 말인데, 그런 피자의 1원당 열량을 출력하는 문제
   • 이해
     • 1원당 열량이 무슨말인지 조금 헷갈려서 고민을 했지만, 적은 돈으로 가장 많은 열량을 가져올 수 있는 피자 라고 바꿔 생각하니 바로 이해가 되었다.
2. 문제를 익숙한 용어로 재정의와 추상화

   • 

   • 문제에서 A,B,C,D 라는 의미가 담겨있지 않은 변수명으로 잡아뒀기 때문에, 시각화를 통해 각 변수가 의미하는 바를 보기 쉽게 하려했다.
   • 그리고 1원당 열량을 식으로 나타내어 분석하고자 했음.
3. 문제를 어떻게 해결할 것인가
   • 1st 접근 - 그리디)
     • 1원당 열량을 식으로 나타내었을때, 우선 도우가격(A)과 칼로리(C)는 고정이므로 이를 제외하고 생각하면
       k개의 D합을 B * k로 나눈 형태의 식 즉, (고른 토핑 열량의 합) / (모든 토핑의 가격)만보면 된다.
     • 1원당 열량이 가장 큰 피자를 골라야하는데,
       토핑의 가격이 너무 비싸면 아무리 높은 열량의 토핑을 고른다해도 의미없을 수 있고,
       토핑의 가격이 너무 싸면 모든 토핑을 다 골라야할 수 있기 때문에, 조건 분기가 조금 필요하다.
     • 열량을 내림차순으로 정렬하여, 가장 열량이 큰 토핑부터 선택하면서 비교했을 때,
       전 계산값보다 현 계산값의 열량이 작아지는 형태라면, 이제 가격이 큰 비율을 차지한다는 말과 같으므로 그 뒤의 계산은 전부 줄어드는 형태일 것이다.
     • 그러므로 전 계산값과 비교하여 열량이 작아지기 전까지 연산을 해주면 된다!
4. 위 계획을 검증
   • 가격을 내림차순하면, 가격이 큰 애들이 앞에 오기 때문에 뒤로갈수록 가격이 작아지는 형태일것이다.
   • 그럼에도 토핑 가격은 모두 동일하므로, 
     내림차순한 토핑열량 리스트의 앞에서부터 진행하면, 뒤로갈수록 가격의 영향이 세질 수 밖에 없다.
   • 그래서 전과 비교하며 작아지기전까지 연산해주면, 최고의 피자를 선택할 수 있다!
5.  계획 수행 (실제코드 작성)
   1. Java 11

      • import java.util.*;
        import java.io.*;
        
        public class Main{
            static int N,A,B,C;
            static Integer[] toppingCal;
            static double prePizzaPrice, prePizzaCal;
            static double curPizzaPrice, curPizzaCal;
        
            public static void main(String[] args) throws IOException {
                //System.setIn(new FileInputStream("src/input.txt"));
                BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
                BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));
        
                N = Integer.parseInt(br.readLine());
                StringTokenizer st = new StringTokenizer(br.readLine());
                A = Integer.parseInt(st.nextToken());
                B = Integer.parseInt(st.nextToken());
                C = Integer.parseInt(br.readLine());
        
                toppingCal = new Integer[N];
                for (int n = 0; n < N; n++) {
                    toppingCal[n] = Integer.parseInt(br.readLine());
                }
                curPizzaPrice = A;
                curPizzaCal = C;
        
                // 그리디를 위한 정렬 - O(NlogN)
                Arrays.sort(toppingCal, Collections.reverseOrder());
        
                // N번 돌면서 전과 비교 - O(N)
                for (int n = 0; n < toppingCal.length; n++) {
                    prePizzaPrice = curPizzaPrice;
                    prePizzaCal = curPizzaCal;
        
                    curPizzaPrice += B;
                    curPizzaCal += toppingCal[n];
                    if(curPizzaCal/curPizzaPrice < prePizzaCal/prePizzaPrice){
                        bw.write((int) (prePizzaCal/prePizzaPrice)+"");
                        break;
                    } else if (n == toppingCal.length-1) {
                        bw.write((int) (curPizzaCal/curPizzaPrice)+"");
                    }
                }
                bw.flush();
        
            }
        }

6. 회고하기
   • 이제 조금씩 그리디에 대해 감을 잡아가는 단계인 것 같다! 어떻게 정렬하여 좋은 애를 취해야하는지 깨닫고 있음
   • 위 문제의 경우에도 딱 떨어지는 식처럼 보이지 않아서 조금 망설였지만, 검증을 통해 분석해보니 결국 흐름이 있었고 이를 그리디적으로 풀어낼 수 있었기 때문에 앞으로도 적절한 접근법을 찾는 연습을 해야겠다 ㅎㅎ

 

• 결과