백준 31963 두 배 문제 풀이
백준 온라인 저지, 31963번: 두 배
도입
각 원소 $A_i$를 두 배하는 연산만 사용하여, 수열을 오름차순으로 만들어야 한다. 두 배 연산을 몇 회 해야하는지 계산하는 것은 2의 거듭제곱의 역연산을 수행하는 것으로 처리 가능하다.
문제 풀이
오름차순 조건을 수열에서 연이은 어떤 두 원소 $A_{i-1}$, $A_i$에 대한 관계식으로 나타낼 수 있다.
\[A_{i-1} 2^x \leq A_i 2^y\]$x$와 $y$는 각각 $A_{i-1}$과 $A_i$에 적용한 두 배 연산의 횟수이다.
반복 과정 상에서 이전 시점에 대한 표현인 $x$는 이미 계산했다고 가정하고, 현재 시점의 $y$를 구하는 것을 목표로 잡는다. 관계식을 $y$에 대해서 다음과 같이 정리할 수 있다.
\[log_2 A_{i-1} + x \leq log_2 A_i + y\] \[log_2 \frac{A_{i-1}}{A_i} + x \leq y\]따라서 $y$는 최소한 $log_2 \frac{A_{i-1}}{A_i} + x$ 이상이다.
$y$는 횟수에 대한 표현이므로 정수값이어야 한다. $log_2 \frac{A_{i-1}}{A_i} + x$가 정수가 아닌 실수인 경우, 최소한 이보다는 큰 정수 중 가장 작은 정수여야 한다. 다시 말해 올림 처리로 $y$를 구할 수 있다.
\[y = \lceil log_2 \frac{A_{i-1}}{A_i} + x \rceil\]마무리
정리한 수식의 계산 결과가 음수인 경우가 있다. 이는 $log$ 함수를 사용하기 때문에 발생하는데, 이미 오름차순 조건을 만족하는 것으로 이해할 수 있다.
\[y = \max(0, \lceil log_2 \frac{A_{i-1}}{A_i} + x \rceil)\]이미 오름차순 조건을 만족하는 경우, 두 배 연산을 수행할 필요가 없으므로 $y$는 0이다. 다시 말해 $y$가 음수인 경우에는 0으로 처리할 수 있다.
대부분의 표준 라이브러리는 $log_2$ 구현을 제공하고 있어, 이를 사용하여 구현하면 어렵지 않게 구현할 수 있다.
다만 이 문제의 유형은 그리디인 모양이다. 그리디한 알고리즘을 구현하기보다 단순 수식 전개로 밀어버렸기 때문에, 이 풀이는 별해에 가까울 것 같다.