문제

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

해설

제트기가 공항들을 순회하는 최단 시간을 계산하는 문제입니다. TSP(Traveling Salesman Problem)는 NP-hard에 속하기 때문에 다항 시간 내에 결과를 구할 수 없기 때문에 주어진 근사식을 사용해 최단 시간을 구합니다. 결과적으로 구해야 하는 총 시간은 근사식을 사용해 최단 경로를 구하는 시간과 제트기가 실제로 순회하는데 걸리는 시간의 합입니다.

구현

1. 근사식을 사용해 최단 경로를 구하는 시간(t1)은 $t_1 = \frac{n}{ p \cdot 10^9 } ( log_{2} n )^{c \sqrt{2}}$ 입니다.
2. 제트기가 실제로 공항들을 순회하는 시간(t2)은 $t_2 = \frac{s}{v} (1 + 1/c)$ 입니다.
3. 구해야 하는 총 시간(t)은 $t = t1 + t2$ 입니다.

매개변수 c이외에 변수들은 모두 문제에서 주어지므로 $t = f(c)$ 꼴의 함수 형태로 정리가 됩니다. 이 함수의 그래프를 잘 생각해 보면 t1은 지수함수지만 곱해진 계수( $\frac{n}{ p \cdot 10^9 }$ )가 매우 작기 때문에 정의역 $\mathbb{R}$ 에서 치역 $\{ t_{1} \in \mathbb{R} : t_1 > 0 \}$ 으로 천천히 증가합니다. 한편, t2는 분수함수인데 정의역 $\{ c \in \mathbb{R} : c \neq 0 \}$ 에서 치역 $\{ t_{2} \in \mathbb{R} : t_2 \neq \frac{s}{v} \}$ 으로 1사분면과 3사분면에 존재합니다.

문제의 정의에서 매개변수 c는 음수가 나올 수 없으므로, 두 함수의 합은 정의역 $\{ c \in \mathbb{R} : c > 0 \}$ 에서 치역 $\{ t \in \mathbb{R} : t > \frac{s}{v} \}$ 으로 존재합니다. c가 작을 때는 t1의 증가량이 t2의 감소량보다 작기 때문에 t가 감소하지만, c가 충분히 커진다면 t1이 지수함수기 때문에 t2의 감소량보다 커져서 증가하게 됩니다.

글로만 설명하기엔 부족한 감이 있어서 예제입력1과 2를 직접 대입해서 WolframAlpha로 구해보았습니다.

1. 예제 입력 1
2. 예제 입력 2

Local minimum 부분을 보면 최솟값일 때의 x와 y(c와 t에 대응)을 볼 수 있는데, 예제 출력과 일치함을 볼 수 있습니다. 즉, t가 최소가 되는 지점이 존재하고 그 값이 정답인 것입니다.

따라서 $t = f(c)$ 는 극값이 한 개만 존재하면서 극값이 아닌 좌표에서는 반드시 증가하거나 감소하는 함수, 즉, 유니모달(unimodal)한 함수라고 할 수 있으며 삼분 탐색으로 답을 구할 수 있습니다.

시간복잡도 계산

소수점 $10^{-6}$ 자리까지 확인하기 때문에 double 범위 내에서 해결이 가능합니다. 0부터 적절한 범위까지 적절한 만큼 반복을 하면 제한 시간을 초과하지 않으면서 충분한 정밀도를 얻을 수 있습니다.

삼분 탐색은 1번 연산할 때마다 답이 될 수 있는 범위(정밀도)가 2/3로 줄어듭니다. 따라서 n번 반복했을 때, 답이 될 수 있는 범위가 (2/3)^n이 됩니다. 1번 연산하는데 걸리는 시간이 tcalc라면 $frac{ (\text{제한시간(초)}) \times 10^9}{t_calc} = n, range \times (\frac{2}{3})^n = (\text{정밀도})$ 라고 할 수 있습니다. 정밀도는 문제에서 주어져 있기 때문에 이를 통하여 삼분 탐색을 할 범위를 계산해 낼 수 있습니다.

소스 코드

http://boj.kr/37151fe73eb943459aa70d89b74e0475

코멘트

포스트를 쓰면서 복기해보니 정말 아무 근거 없이 삼분 탐색의 범위와 반복 횟수를 정했습니다. 테스트케이스는 잘 통과했지만, 위험한 발상이었고 다음부터는 조심해야겠습니다.

---

참고