백준 9206: 나무 말고 꽃

※이전 블로그에서 가져온 글입니다※

---

[Platinum III] 나무 말고 꽃 - 9206

문제 링크

성능 요약

메모리: 33240 KB, 시간: 40 ms

분류

미적분학, 수학, 수치해석

제출 일자

2024년 3월 5일 12:53:25

문제 설명

선영이와 남자친구의 2주년이 얼마 남지 않았다. 선영이는 그를 위해 특별한 것을 사주려고 한다. 남자친구는 나무에 관심이 매우 많다. 하지만, 선영이는 나무는 선물로 매우 크다고 생각한다. 따라서, 꽃을 사주려고 한다.

선영이는 모든 꽃에는 그 꽃과 가장 잘 어울리는 꽃병의 부피가 있다고 생각한다. 선영이는 꽃병을 구매하기 위해 인터넷 쇼핑몰에 들어갔다. 쇼핑몰에는 꽃병의 사진과 윤곽 함수가 적혀져 있다. 가장 적합한 꽃병을 찾는 프로그램을 작성하시오.

꽃병의 윤곽은 함수 f(x) = a・e^-x2+ b・√x로 나타낼 수 있다. 여기서 x는 꽃병의 바닥과 떨어진 수직 거리이다. 꽃병은 이 함수를 x축에 대해서 회전시킨 모양이다. 꽃병의 높이는 h이다.

서로 다른 두 꽃병의 부피의 차이는 적어도 10^-4이다. 또, 서로 다른 두 꽃병과 선영이가 찾는 꽃병의 부피의 차이도 적어도 10^-4 만큼 차이난다.

입력

첫째 줄에 선영이가 찾는 꽃병의 부피 1 < V ≤ 10⁵ 와 쇼핑몰에 올라와 있는 꽃병의 수 0 < N ≤ 5 이 주어진다.

다음 N개 줄에는 문제의 함수에 해당하는 a, b, h가 주어진다. (1 ≤ a, b, h ≤ 10)

예제의 경우에 두 꽃병의 부피는 34.72348, 21.77966이다.

출력

선영이가 찾는 꽃병과 부피 차이가 적은 꽃병의 인덱스를 출력한다. 첫 번째 꽃병의 인덱스는 0이다.

---

이 문제는 단순히 $ \pi \int_{0}^{h}(ae^{-x^{2}}+b\sqrt{x})^{2}dx$를 계산하면 되는 문제입니다. 이를 계산하면 다음과 같습니다:

$$\frac{1}{4}\pi (a^{2}\sqrt{2\pi}\textrm{erf}(\sqrt{2}h)+2b(bh^{2}-2ah^{\frac{2}{3}}\textrm{E}_{\frac{1}{4}}(h^{2})+2a\Gamma (\frac{3}{4})))$$

따라서 위 식을 계산하는 코드를 작성하면 됩니다. Error Function과 Exponential Integral E, 그리고 Gamma Function을 구현하도록 하겠습니다.

 

Error Function

Error Function은 다음과 같이 정의됩니다.

$$ \mathrm{erf}(x) = \frac{2}{\sqrt{\pi}} \int_{0}^{x} e^{-t^2}\, dt $$

직접 Error Function을 계산해도 되나, 다행히도 math 모듈에 math.erf() 함수가 있습니다.

 

Exponential Integral E

Exponential Integral E는 다음과 같이 정의됩니다.

$$ \mathrm{E_{n}}(x) = \,\mathrm{} \int_{1}^{\infty} \frac{e^{-xt}}{t^{n}} \, dt $$

그리고 Upper Incomplete Gamma Function으로도 정의될 수 있습니다. 여기서 이 정의를 사용하도록 하겠습니다.

$$ E_{n}(x) = x^{\,n-1} \,\Gamma(1 - n,\, x) $$

Upper Incomplete Gamma Function은 다음과 같이 정의됩니다.

$$ \Gamma(s, x) = \int_{x}^{\infty} t^{\,s-1}\, e^{-t} \, dt $$

이를 이용해, 최종적으로 Gamma Function으로 나타낸 식은 다음과 같습니다.

$$E_{n}(x)
= x^{\,n-1}
  \Biggl(
    \Gamma(1 - n)
    \;-\;
    x^{\,1-n}
    \sum_{i=0}^{\infty}
      \frac{x^{\,i}}{\Gamma(2 - n + i)}
      \, e^{-x}
  \Biggr)$$

다음은 Exponential Integral E를 구현한 코드입니다.

def E(n, x):
    tmp=0.0
    for i in range(inf):
        tmp+=(math.pow(x, i)/math.gamma(1-n+i+1))
    return math.pow(x, n-1)*(math.gamma(1-n)-math.pow(x, 1-n)*tmp*math.gamma(1-n)*math.pow(math.e, -x))

 

코드 최종 구현

앞서 언급한 공식들을 이용해 꽃병의 부피를 구하는 함수를 만들 수 있습니다. 다음은 꽃병의 부피를 구하는 함수를 구현한 코드입니다.

def bottle(a, b, h):
    return 0.25*(math.sqrt(2*math.pi)*math.pow(a, 2)*math.erf(math.sqrt(2)*h)+2*b*(-2*a*math.pow(h, 1.5)*E(1/4, math.pow(h, 2))+2*a*math.gamma(3/4)+b*math.pow(h, 2)))*math.pi