BOJ 5163 - Isn't It Funny How a Bear Likes Honey?

문제

BOJ 5163 - Isn't It Funny How a Bear Likes Honey?

꿀단지(honey jar)에 꿀이 가득 담겨 있고, 곰(bear)이 구형 입 모양으로 꿀을 퍼먹는다. 각 한 번의 입질(bite)이 반지름 t인 구(sphere)만큼의 꿀을 덜어낸다고 할 때, 모든 입질 이후에도 꿀이 남아있으면 "No", 다 먹어치웠으면 "Yes"를 출력한다.

구의 부피 공식은 V = (4/3) * PI * r^3 이다. 단위는 그램(g)이고 꿀의 밀도는 1000g/L이다.

입력

• 첫째 줄에 데이터 세트 수 R이 주어진다.
• 각 데이터 세트마다:
  • 한 줄에 입질 횟수 bols와 꿀의 무게 weight가 주어진다.
  • 이후 bols개의 줄에 각 입질의 반지름 t가 주어진다.

출력

각 데이터 세트마다 Data Set i: 헤더와 함께 꿀이 남아있으면 No, 다 먹었으면 Yes를 출력한다. 데이터 세트 사이에 빈 줄을 출력한다.

예제

풀이

각 입질마다 구의 부피를 계산하고, 이를 무게로 환산해 꿀의 총 무게에서 차감한다.

1. R개의 데이터 세트를 처리한다.
2. 입질 횟수 bols와 초기 꿀의 무게 weight를 입력받는다.
3. 각 입질의 반지름 t에 대해 구의 부피 (4/3) * PI * t^3을 계산한다.
4. 부피(단위: L)에 1000을 곱한 값이 그램이므로, weight -= (4/3 * PI * t^3) / 1000을 반복 수행한다.
5. 모든 입질 후 weight가 0 이상이면 "No", 음수이면 "Yes"를 출력한다.

핵심 아이디어: 구의 부피 공식 (4/3) * PI * r^3을 그대로 적용한다. 코드에서는 (t * t * t * 4) / 3 * PI / 1000 형태로 단위 변환과 함께 계산한다.

코드

#include <iostream>
 
const double PI = 3.1415926535897932384;
 
using namespace std;
 
int main()
{
  int r, bols;
  cin >> r;
  double weight, t;
  for (int i = 1; i <= r; i++)
  {
    cin >> bols >> weight;
    while (bols-- > 0)
    {
      cin >> t;
      weight -= ((t * t * t * 4) / 3 * PI) / 1000;
    }
 
    cout << "Data Set " << i << ":\n"
         << (weight >= 0.0 ? "No" : "Yes") << "\n\n";
  }
}

복잡도

• 시간: O(R * B) — R개의 데이터 세트, 각 세트의 입질 횟수 B만큼 반복
• 공간: O(1) — 상수 개의 변수만 사용