BOJ 4573 - Pizza Pricing

문제

여러 피자의 지름과 가격이 주어질 때, 단위 면적당 비용이 가장 저렴한 피자의 지름을 출력하는 문제

풀이

피자의 면적은 지름의 제곱에 비례하므로(π는 공통), 가격을 d²로 나눈 값이 가장 작은 피자를 선택한다. 각 메뉴별로 가장 저렴한 피자의 지름을 출력한다.

코드

#include <iostream>
 
using namespace std;
 
int main() {
  ios_base::sync_with_stdio(false);
  cin.tie(NULL);
 
  int n, menuCount = 1;
  while (cin >> n && n != 0) {
    int bestDiameter = 0;
    double minCostPerSqInch = 1e18;
 
    for (int i = 0; i < n; i++) {
      double d, p;
      cin >> d >> p;
 
      double currentCost = p / (d * d);
 
      if (currentCost < minCostPerSqInch) {
        minCostPerSqInch = currentCost;
        bestDiameter = (int)d;
      }
    }
 
    cout << "Menu " << menuCount++ << ": " << bestDiameter << "\n";
  }
  return 0;
}

복잡도

시간: O(N) (N: 피자 개수)
공간: O(1)

문제

풀이

코드

복잡도

최근 글