BOJ 5720 진법 알아내기

먼저 수식을 파싱하여 진법을 $x$로 하는 방정식을 세웁니다. 이 방정식은 고차방정식일 가능성이 있으므로, 최소 진법을 $x_0$라고 할 때 이 값부터 순차적으로 대입하여 0이 나오면 답으로 출력하는 방법을 쓸 수 있습니다.

이때 여러 가지 엣지 케이스에 주의해야 합니다.

• 다항식이 0이라면 가능한 진법은 $x_0$ 이상의 모든 진법입니다.
• 다항식이 0이 아닌 상수라면 가능한 진법은 없습니다.
• 다항식이 일차식일 경우, 10=9*9*9*9*9*...*9와 같이 오래 걸리는 식을 만들 수 있으므로, 따로 직접 해결합니다.

그 외의 경우, 탐색을 멈출 $x$값을 정해야 하는데, 최고차항의 값과 나머지 항들의 절댓값의 합을 비교하여 전자가 크면 멈추는 방법을 사용할 수 있습니다. 이렇게 하면 문제 조건에서 만들 수 있는 2차 이상의 모든 방정식에 대해 충분히 빠르게 멈추게 됩니다.