/<> 백준 14346, 14347: Radioactive Islands

Darkpppet·2024년 9월 2일

백준 수치해석 수학 알고리즘

백준

목록 보기

5/5

/<> 백준 14346: Radioactive Islands (Small) [solved.ac Ruby V]

https://www.acmicpc.net/problem/14346

/<> 백준 14347: Radioactive Islands (Large) [solved.ac Ruby IV]

https://www.acmicpc.net/problem/14347

문제 요약

$(-10, A)$ 에서 $(10, B)$ 까지 1의 속도로 보트를 타고 이동한다.
$(0, C_i)$ 에는 섬이 있다.

이동 시, 매 순간 1초당 1만큼 방사능을 받는다.
각 섬에 대해 거리를 $D_i$ 라 하면, 매 순간 섬마다 $1\over{D_{i}^2}$ 만큼의 방사능을 받는다.

이 때, 받는 방사능의 총합을 최소로 하는 경로로 이동했을 때의 받는 방사능 총합을 구하라

조건

모든 $i$ 에 대해 $-10.00 ≤ A, B, C_i ≤ 10.00$

14346(Small)은 섬이 1개, 14347(Large)은 섬이 1~2개
섬은 겹치지 않는다.

풀이

풀이 과정을 요악하면

최적 경로에 관한 미분방정식을 구한다 (변분법; 오일러-라그랑주 방정식)
구한 미분방정식으로 최적 경로를 구한다 (룽게-쿠타 방법)
최적 경로로 이동할 때의 방사능 총합을 구한다 (심슨 공식)

로 풀 수 있다.

Small을 먼저 해결하자.

step 1. 최적 경로에 관한 미분방정식 구하기

섬의 좌표가 $(0, 0)$ 이 되도록 좌표를 평행이동 하여도 경로 및 총 방사능 양은 변하지 않는다. 따라서 계산을 편리하게 하기 위해 섬의 좌표를 $(0,0)$ 으로, 시작점과 끝점을 각각 $(-10, A-C)$ , $(10, B-C)$ 로 하자.

시간 $t$ 일 때 보트의 좌표는 $(x(t), y(t))$ 이다.
이 때, 도착 시 까지 방사능의 총합은

$\displaystyle \int_{0}^{t_1} 1+{1 \over x^2 + y^2} dt$ (단, $t_1$ 은 끝점에 도달한 시간)

이 값을 최소로 해야 하는데 생긴게 오일러-라그랑주 방정식을 쓰고싶게 생겼다.

그런데, 위 식으로 변분법을 사용하려면 문제가 있다.

$\displaystyle \int_{0}^{t_1} 1+{1 \over x^2 + y^2} - \lambda(\sqrt{\dot x^2 + \dot y^2 }-1) dt$

이 식에 대한 오일러-라그랑주 방정식을 풀어야 하는데, 변수가 $x, y, \lambda, t_1$ 으로 너무 많다.

생각을 조금 해 보면 $y$ 를 $x$ 에 관한 식( $f(x)$ )으로 생각하고 $t$ 를 제거할 수 있다.
이를 바탕으로 식을 변형하면

$\displaystyle v = \sqrt{\dot x^2 + \dot y^2} = \sqrt{({dx \over dt})^2 + ({dy \over dt})^2}= 1$
$\displaystyle \Rightarrow ({dx \over dt})^2 + ({dy \over dt})^2= 1$
$\displaystyle \Rightarrow dx^2+dy^2 = dt^2$
$\displaystyle \Rightarrow dt = \sqrt{dx^2 + dy^2} = \sqrt{1+({dy \over dx})^2} dx$

$\displaystyle \therefore \int_{0}^{t_1} 1+{1 \over x^2 + y^2} dt = \int_{-10}^{10} (1+{1 \over x^2 + f(x)^2}) \cdot \sqrt{1 + f'(x)^2} dx$

제약조건을 사용하여 $t$ 를 제거하였으므로, $\lambda$ 도 없어도 된다.

위 값이 최소가 되도록 하는 경로를 구하기 위해 오일러-라그랑주 방정식을 사용하면,

$\displaystyle F = (1+{1 \over x^2 + f^2}) \cdot \sqrt{1 + f'^2}$

$\displaystyle {\partial F \over \partial f} - {d\over dx}({\partial F \over \partial f'}) = 0$

을 풀면 된다.

식이 매우 더러워서 정리 과정은 생략하고

$\displaystyle f'' = {{2(f^2+1)(xf'-f)} \over {(x^2+f^2)(x^2+f^2+1)}}$

를 얻는다.

step 2. 구한 미분방정식으로 최적 경로 구하기

룽게-쿠타 방법을 사용하자.
2차 미분방정식이므로 식을 2개 만들어서 $f$ 와 $f'$ 을 구할 수 있다.

$y_1 = f'$
- $\displaystyle y'_1 = f'' = g_1(x, f', f) = g_1(x, y_1, y_2) = {{2(y_2^2+1)(xy_1-y_2)} \over {(x^2+y_2^2)(x^2+y_2^2+1)}}$
- $y_1(-10) = f'(-10) = ?$
$y_2 = f$
- $y'_2 = f' = g_2(x, f', f) = g_2(x, y_1, y_2) = y_1$
- $y_2(-10) = f(-10) = A-C$

그런데, $y_1(-10)$ 값(시작 기울기)이 정해져있지 않고, 우리가 알고있는 $y_2(10)=B-C$ 값이 사용되지 않았다.

시작 기울기를 잘 지정해주어야 하는데, 이를 위해 여러 값들을 조사하여 시작 기울기와 끝점의 관계를 알아보면

시작 기울기와 끝점의 관계는 이러한 개형의 그래프이다.
수치적으로 구하여서 정확한 값은 아니지만, 대략적으로 아래와 같은 특징들이 있다.

모든 구간에서 증가한다
$f'(-10)=-{A-C \over 10}$ 을 점근선으로 갖는다.
점근선 근방에서 값이 급격하게 증가하여 점근선에서 값이 발산한다
점근선 근방이 아닌 곳에서는 근사적으로 선형적으로 증가한다.

이를 실제 문제와 비교 해 보면

점근선은 시작점과 섬을 연결한 직선의 기울기이다
- 즉, 시작점과 섬을 연결한 방향으로 출발하면 받는 방사능의 양은 발산한다.
점근선 왼쪽은 직선의 아래, 점근선 오른쪽은 직선의 위쪽이다

따라서 점근선을 기준으로 두 구간으로 나누어 이분탐색으로 $f(10)=B-C$ 인 $f'(-10)$ 값을 각각 찾고, 각 $f'(-10)$ 에 대한 경로 중 방사능 총합이 더 적은 값이 구하는 값이다.

*내용 추가
위 방법은 경계값 문제를 초기값 문제로 바꾸는 일종의 shooting 방법입니다.

step 3. 방사능 총합 구하기

심슨 공식을 사용하여 아래 값을 계산한다

$\displaystyle \int_{-10}^{10} (1+{1 \over x^2 + f(x)^2}) \cdot \sqrt{1 + f'(x)^2} dx$

Large에서의 변경점 (섬이 2개일 경우)

좌표의 변환이 굳이 의미가 없으므로 좌표 변환을 생략한다. 대신 WLOG $C_0 < C_1$ 로 하자.
방사능 총합 식이 아래로 바뀐다.

$\displaystyle \int_{-10}^{10} (1+{1 \over x^2 + (f(x) - C_0)^2} + {1 \over x^2 + (f(x) - C_1)^2}) \cdot \sqrt{1 + f'(x)^2} dx$

마찬가지로 미분방정식도 아래로 바뀐다

$\displaystyle f''=-{{2(f'^2+1)({{xf' - f + C_0} \over{(x^2+(f-C_0)^2)^2}}+{{xf' - f + C_1} \over{(x^2+(f-C_1)^2)^2}})} \over {1 + {1 \over x^2 + (f-C_0)^2} + {1 \over x^2 + (f-C_1)^2}}}$
$f'(-10)$ 값 별 $f(10)$ 값 그래프가 아래와 같이 바뀐다.