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로 떨어졌다. 다이아라고 하기엔 쉬운 것 같긴 하다.