이동식 저장소

뭔가 흥미로운 수학 이야기가 있다. 문제에서 시키는 대로 구현하면 된다.

단, 아주 나이브하게 이중 반복문으로 구현하면 시간 초과가 난다. 다음의 세 가지를 고려해야 한다.

1. $\frac{1}{x}\le \frac{a}{b}$인 최대의 $\frac{1}{x}$ 찾기

부동 소수점 연산을 피하기 위해 수식을 $b\le ax$로 바꾸자. 조건을 만족하는 가장 큰 $\frac{1}{x}$를 찾으려면 가장 작은 $x$를 찾으면 된다.

물론 $x=b$부터 시작하여 조건을 만족하지 않을 때까지 $x$를 $1$씩 감소시켜도 된다. 그러나 문제에서 테스트케이스의 수 $T$가 주어지지 않았고, 이 방법을 사용하면 시간복잡도 $O(T{b}^2)$로 시간 초과를 피하기 어려워 보인다.

따라서 이분 탐색(이진 탐색 아니다!)을 사용하여 $O(\log b)$ 시간에 $x$를 찾아야 한다. $left=1,right=b+1$로 두고 $[left,right)$ 구간의 $mid$를 계산하여 $x$를 찾으면 된다. 이렇게 하면 전체 시간복잡도가 $O(Tb\log b)$로 시간 초과를 피할 수 있다.

2. 자료형

분수가 등장하는 문제는 웬만하면 실수형을 사용하지 않는 것이 좋다. 웬만하면 나는 분자와 분모를 각각 정수형으로 놓고 계산한다. 여기서는 분자를 $a$, 분모를 $b$라고 하자.

$\frac{a}{b}-\frac{1}{x}=\frac{ax-b}{bx}$에서 문제의 조건에 의해 $bx<2^{31}$이므로 $bx$는 int 자료형에 담을 수 있다. 하지만 $ax-b$는 int의 범위를 넘어갈 수 있으므로 $a$와 $b$를 64비트 정수형으로 저장하는 것이 안전하다.

3. $a$가 $b$의 배수일 경우

$a$와 $b$의 최대공약수를 $gcd$라고 하면, $\frac{a}{b}$는 기약분수 $\frac{1}{b/gcd}$로 나타낼 수 있다. $a/gcd=1$인 이유는 $a$가 $b$의 배수이므로 $b=a\times gcd$ 꼴로 나타낼 수 있기 때문이다. 이처럼 분자가 1인 경우 분모가 정답이므로 계속 계산할 필요 없이 즉시 정답을 출력해야 한다. 안 그러면 시간초과 난다.