BOJ 17454 - 갓

BOJ 17454 - 갓

힘들었던 수학문제이다.

만약 $HD > HS$나 $SD > SH$ 라고 하자. 그럼 항상 가능하다.

세 번의 투표들에서 계수를 각각 $x,y,z$ 라고 하자.

$x=1$ 여야 한다. $H,S$ 에게 가능한 적은 표를 주어야 하기 때문이다.

$D$가 $H$를 이겨야 한다고 해보자. 각각 받은 투표수를 $f(D), f(H), f(S)$라 하자.

$f(D)=y \cdot HD + z \cdot SD$ 이고

$f(H)=DH+z \cdot SH$ 이다.

$f(D) > f(H)$ 여야 하므로

이 반평면은 $(y,z)$ 좌표계를 따지면 $\left(\dfrac{DH}{SD-SH}, 0\right)$ 를 지나고 다음과 같이 그려진다.

기울기는 아래처럼 항상 그려지지 않는다.

마찬가지로 $f(D) > f(S)$ 가 되는 식을 구하면 어떠한 반평면이 나오고 결국 정답은 겹치는 반평면 좌표 $(z,y)$ 가 있는지에 대한 문제로 환원된다.

공식 해설 링크를 참고해서 풀어보자!

참고로 나는 이 문제를 37틀했다.