https://www.acmicpc.net/problem/19956
문제요약
- 바이러스를 배양중임
- 제곱하거나, p(소수)로 나눌 수 있음(나누어떨어져야함)
- 가장 적은 수의 시퀀스로 n->m을 만들어야함
접근법
- 소인수 개수를 맞춰줘야하는데 증가는 제곱만 가능하고, 감소는 나누기만 가능함을 파악
- 일단 소인수 분해
- 1은 예외처리(해도 되고 자연스럽게 구현해도 되고)
- m에 있는 소인수가 n에 없으면 실패처리
- 제곱은 소인수의 개수가 적을때만 수행 : 더 많은데 굳이 늘릴 필요는 없다고 봄
- 나누기는 언제든 수행
- BFS로 최단거리 파악
- 방문할 노드가 1 ~ 10^9가 될 것처럼 보이지만
- 지수는 최대 30개이고, 소인수는 2,3,5,7,11,13,17,19,23 해도 9개 정도 됨
- 9개정도의 소수로 10^9 아래에서만 유지하는 경우의 수는 많지는 않을 것으로 판단함
- 최단거리 이동경로를 잘 정리해서 출력
newbieski