BOJ 8222 - Distance

지난 글에서 추천받은 대로 이번에는 OI Checklist에서 문제를 골라 보았다. OI Checklist에서 하나를 뽑으려니 감이 잘 안와서 POI 문제들이 많은 https://www.acmicpc.net/workbook/view/1939에 가 하나를 골라 보았다. 고른 문제는 POI 2012의 Distance이다. 

 

문제 요약

두 자연수 $x, y$의 거리 $d(x,y)$를 $x$에 소수를 곱하거나, 나누는 연산을 해 $y$에 도달하기 위한 최소 연산 횟수로 정의하자. 배열 $A$가 주어질 때, 각 $i$에 대해서 $d(A_i,A_j)$가 최소가 되는 $j$를 구하여라.

 

풀이

우선, 같은 수가 여러 개 있는 경우는 전처리로 해결해 줄 수 있으므로 모든 수가 다르다고 가정하자.

$x$에서 $y$로 이동하는 법은 $g = gcd(x,y)$를 거치는 것이 최적이다. 즉, $f(x)$를 $x$의 소인수 개수라 하면 $d(x,y) = f(\frac{x}{g}) + f(\frac{y}{g}) = f(x) + f(y) - 2*f(g)$이다. $g$와 $x$를 고정하면 $f(y)$의 최솟값만 보면 되므로, $g$의 배수들 중 $(f(x),i)$ pair가 가장 작은 두 쌍을 저장해주는 방식으로 해결할 수 있다. $f(i)$는 소수 거듭제곱에 대해 체와 같은 방식으로 구해줄 수 있다. 배수를 보기 때문에 시간 복잡도는 $O(MX log MX)$이다.

 

문제를 풀고 나서 팀원 선배들한테 추천해줬더니 다들 빨리 풀고 기여해서 티어가 D5에서 P1로 떨어졌다. 다이아라고 하기엔 쉬운 것 같긴 하다.