Tip - 두 정수의 중앙값을 안전하게 구하기

March 20, 2023

중앙값 구하기의 Overflow

우리가 특정 문제에서 $\left\lfloor \dfrac {L+R}2 \right\rfloor$ 의 값을 구해주어야 할 때, $L+R$ 은 overflow가 날 수도 있는 상황이 있을 수 있다.

이 때, $\left\lfloor \dfrac {L+R}2 \right\rfloor = L+\left\lfloor \dfrac {R-L}2 \right\rfloor$ 라는 사실을 이용하여 overflow를 피해줄 수 있다.

$\left\lfloor \right\rfloor$ 이 없다면 저 식은 실수에서 성립하는데 정수에서도 성립할까?

$R-L$ 도 짝수이다. $R$과 $L$이 모두 짝수일 때는 자명하고 $R$과 $L$이 모두 홀수일 때도 옳다.

따라서 $\left\lfloor \right\rfloor$ 에 영향을 받지 않으므로 식이 성립한다.

$R-L$ 도 홀수이다. 위와 비슷한 방식으로 유도할 수 있다.

$\left\lfloor \dfrac {L+R}2 \right\rfloor = L+\left\lfloor \dfrac {R-L}2 \right\rfloor$ 에서,

좌변은 $\dfrac {L+R-1}2$ 가 되고, 우변은 $L+\dfrac {R-L-1}2$ 이되는데,

$L+\dfrac {R-L-1}2 = \dfrac {R+L-1}2$ 가 되어 결국 양변이 같음이 보여진다.