[C++] 백준 5545번 최고의 피자

1원당 열량이 가장 높은 피자를 만들 때 그 열량이 얼마인지 출력하는 문제입니다.

도우를 반드시 올려야하며 토핑은 선택할 수 있습니다. (같은것 두개 선택 불가)

가격은 도우가격 + (토핑가격 * 토핑갯수) 입니다.

이 때 가장 높은 열량을 만들 수 있는 방법을 찾는 문제입니다.

 

(예제 풀이)

1원당 열량을 구하려면 열랑/가격을 해주었습니다.

200 / 12 = 16.666  (도우의 1원당 열량)

50 / 2 = 25       (토핑1 1원당 열량)

300 / 2 = 150    (토핑2 1원당 열량)

100 / 2 = 50     (토핑3 1원당 열량)

 

먼저 도우의 1원당 열량 보다 높은 수치가 있는지 확인을 합니다.

없다면 도우만 올리는것이 최고의 피자를 만드는 것입니다.

있다면 높은 숫자를 먼저 도우와 합치고 다시 계산을 합니다.

200 + 300 = 500 (도우 열량 + 토핑2 열량)

12 + 2 = 14 (도우 가격 + 토핑2 가격)

500 / 14 = 35.714 (도우 + 토핑2의 1원당 열량)

토핑1은 35.714보다 낮은 25이므로 올리지 않습니다.

토핑3은 35.714보다 높은 50이므로 다시 합치는 방법으로 문제를 해결합니다.

 

(코드 풀이)

토핑 열량이 높은 순서대로 비교를 하기위해 처음 값을 넣을때

내림차순으로 정렬을 해주었습니다.

그리고 도우의 1원당 열량보다 토핑의 1원당 열량이 높을경우

토핑의 높은 순대로 하나씩 합치면서 비교하는 과정을 반복해서 풀었습빈다.

 

#include <iostream>
using namespace std;

int main(int argc, char *argv[])
{
   int N;   // 토핑 종류
   int A;   // 도우 가격
   int B;   // 토핑 가격
   int C;   // 도우 열량
   int D[100];   // 토핑 열량
   int value;   //총 열량
   int price;   //총 가격
   int temp;   // 스왑

   cin >> N;
   cin >> A;
   cin >> B;
   cin >> C;
   for (int i = 0; i < N; ++i) {
      cin >> D[i];
      int j = i;
      while (j != 0 && D[j] > D[j-1]) {   // 내림차순 정렬
         temp = D[j-1];
         D[j-1] = D[j];
         D[j] = temp;
         j--;
      }
   }
   value = C;
   price = A;
   for (int i = 0; i < N; ++i) {
      if (C / A < D[i] / B) {
         C += D[i];
         A += B;
      }
   }
   cout << C / A;

   return 0;
}