BOJ 19847 - 여우 신탁
내 풀이
$x_i \ge x_{i-1}$ 라면 결과값에 영향을 못미치므로 단조감소 수열로 만들자.
어떤 $k$ 에서 시작해서 값이 변화되는 꼴을 관찰하면 항상 2배 이상씩 감소한다는 것을 알 수 있다.
왜냐면 최대한 값이 크게 유지되려면 $\left\lfloor \dfrac{k}{2} \right\rfloor+1$ 정도로 나머지를 취해야 하기 때문이다.
따라서 $0 \to x_0 - 1$ 까지의 수들에 대해 항상 $O(\log MAX)$ 로 결과적으로 어떤 나머지가 되는지 검사해줄 수 있고 경우의 수를 세서 $x_0$ 으로 나누면 정답이다.
정해?
동일하게 단조감소 수열로 만들면 $MAX$ 부터 시작해서 나머지가 변하는 값들을 $O(MAX)$ 개로 한정해줄 수 있어서 큰것부터 나눠서 작은 나머지로 이전시키는 과정을 하면 $O(MAX)$에 풀 수 있다.
Comments