Project Euler Problem 587

와-! 시험 끝났다-!

종강하고 문제 다시 풀기 시작하려고 하는데... 빡센 문제도 풀어봐야겠지만, 역시 랭작하는 재미는 또 다른 얘기니까 

Project Euler에서 쉬운 문제를 하나 먹고 지나가자. 엥간하면 PE는 15% 이상부터는 포스팅을 다 해두려고 한다.

 

https://projecteuler.net/problem=587

 

난이도 : 20%

 

 

문제 설명

 

그림에서, 파란색 영역을 L-section이라고 하자.

그리고, 오른쪽 그림처럼 선을 그었을 때 잘리는 아래 부분(주황색)을 Concave triangle이라고 하자. 

원이 한 개일 때는 그림에서 볼 수 있듯이, Concave Traingle이 L-section의 50% 넓이를 갖는다.

그러나, 원이 2개일 때는 위 그림처럼 넓이의 비율이 50%가 되지 않는다. 실제로 원이 2개일 때는 36.46%이다.

 

원이 $n$개일 때, 처음으로 넓이의 비율 (즉, Concave Triangle / L-section) 이 0.1%보다 작아지는 최초의 $n$을 찾자.

 

 

풀이

처음에 드는 생각은, 이 문제를 어떻게 기하적으로 잘 풀어볼 수 없는가? 하는 것인데, 상당히 불편한 요소가 많아 보인다. (내 기하 실력이 부족해서일 수도 있지만...)

그다음은 해석기하를 도입해 보자. 원의 반지름이 각각 1씩이라고 하면, L-section의 넓이는 $1 - \frac{\pi}{4}$ 임을 알 수 있다. 또한, 원과 직선이 만나는 점을 $(t, \frac{t}{n})$ 이라고 둘 수 있겠다.

원의 방정식은 양함수로 나타낼 수 없지만, 어차피 우리가 필요한 것은 원의 아랫부분이므로  $y = 1-\sqrt{1-(x-1)^2}$ 로 써도 된다.

그러면 결국 우리가 원하는 Concave triangle의 넓이는 

$$\frac{t^2}{2n} + \int_{t}^{1} 1-\sqrt{1-(x-1)^2} \ dx$$

이렇게 쓸 수 있는데... 오른쪽 함수가 적분이 되나? 사실 $\arctan$ 같은걸 잘 써서 $t$를 잘 표현하고 치환적분해도 되긴 될 것 같...기도 한데. 이시점부터 "아 그냥 수치적분 해야겠다" 라는 생각을 했다.

(여담으로, 적분이 되긴 된다.)

아무튼, 저 식을 계산하고 싶지는 않으므로 수치적분을 짜자.

일단 가장 간단한 직사각형 근사 (구분구적법) 을 써본 다음, 안되면 심프슨 공식을 쓰던 가우스 수치적분을 쓰던 할 생각으로 일단 구분구적을 돌리기로 했다. 숫자가 매우 작으므로 파이썬을 쓰자.

 

빠르게 답을 얻기 위해, 필요한 원의 개수를 이분탐색으로 찾을 수 있다. $n$개의 원으로 0.1%보다 작다면, 그보다 많은 원을 놓더라도 0.1%보다 작을 것임이 자명하기 때문이다. 

import time
from math import sqrt, pi

def f(x, n):
	return min(x/n, 1-sqrt(1-(x-1)*(x-1)))

def solve(n):
	step = 1 / 10000
	A = 0
	for i in range(10000):
		u = step * i
		v = step * (i+1)
		tmparea = step * (f(u, n) + f(v, n))/2
		A += tmparea
	return A

def main():
	Lsec = 1-pi/4
	lo = 1
	hi = 100000
	while lo<hi:
		mid = (lo+hi)//2
		ratio = solve(mid)/Lsec*100
		if ratio < 0.1:
			hi = mid
		else:
			lo = mid+1
	print(lo, solve(lo)/Lsec)

if __name__ == "__main__":
	start_time = time.time()
	main()
	print("--- %s seconds ---" % (time.time() - start_time))