[Python] 백준 10791 - Qanat

너비가 $w$이고 높이가 $h$인 직각삼각형 모양의 $\mathsf{Qanat}$가 있습니다. 초기 상태에는 구멍이 뚫려있지 않으며 왼쪽 꼭짓점과 위쪽 꼭짓점에서 물을 끌어 올립니다.

추가적으로 수직 구멍을 $n$개 뚫으면 구멍을 뚫은 삼각형 빗변에서 추가적으로 물을 끌어 올릴 수 있습니다.

물을 끌어 올릴 때에는 추가 비용이 들어가는데, 이 때 $n$개의 수직 구멍을 적절히 뚫어 물을 끌어 올리는데 사용되는 비용을 최소화시키는 문제입니다.

구멍을 뚫은 좌표를 $x_1,x_2,x_3\cdots x_n$라고 했을 때, 비용에 대한 수식은 아래와 같습니다.

이 때 간단한 수학적 계산을 통하여 $a_1$=$\frac{1}{2},$ $k_i=\frac{1-r^2}{4a_i}$, $a_{i+1}=\frac{1}{2}-a_ik_i^2$ 라는 사실들을 알 수 있습니다. ( 이 때, $r=\frac{h}{w}<1)$

모든 $i$에 대해 $0<k_i<1$을 만족하므로 $f_{(x)}$의 최솟값은 $C$라는 사실을 알 수 있고, 그 때 $x_1,x_2,x_3\cdots x_n$의 값들도 구할 수 있습니다.

a = [0]
k = [0]
w, h, n = map(int, input().split())
x = [w]
r = h / w
a.append(0.5)
for i in range(1, n + 1):
    k.append((1 - r * r) / a[i] / 4)
    a.append(0.5 - a[i] * k[i] * k[i])
result = (a[n + 1] - 0.5 + (r + 1) ** 2 / 4) * w ** 2
for i in range(n + 1)[::-1]:
    x.insert(0, x[0] * k[i])
print(f'{result:.6f}')
i = 1
while i <= n and i < 11:
    print(f'{x[i]:.6f}')
    i += 1