16800. 구구단 걷기

16800. 구구단 걷기

문제

풀이

처음엔 최단거리라 생각해서 heapq를 사용한 BFS를 하였다. 하지만 10^12의 상당히 큰 숫자로 인해 TLE가 발생하였다.
최적화로 생각한 것은 약수이다.
50을 예로 들자면 50의 약수는 => 1, 2, 5, 10, 25, 50이다.
(1, 50), (2, 25), (5, 10)이고 맨 마지막 (5, 10)이 답이 될 것이다.
(4, 9) => 13
이 것을 코드화 하면 다음과 같다.

for문을 돌 때 n까지 돌 필요가 없다. 왜냐하면 제곱근기준으로 끝나기 때문에 제곱근까지 해준다. 그러면 num에는 맨 마지막 값이 저장되고 row, col은 각각 1부터 시작하므로 2를 빼줘야 한다.