https://swexpertacademy.com/main/solvingProblem/solvingProblem.do

문제 개요

무한히 많은 행과 열이 있는 곱셈표에 (i,j)셀에는 ixj 가 적혀 있습니다. (1,1)에서 시작하고 오른쪽과 아래로만 이동할 수 있다고 할 때 정수 N에 도달하기 위한 가장 적은 이동횟수는?

문제 접근

문제에서 정수 N의 값을 $2\leq N\leq10^{12}$ 이라고 줬기 때문에, 브루트포스 방식으로는 해결할 수 없습니다.

그렇다면 어떤 수학적 방법이 필요하다는 의미이니, 힌트를 살펴봅니다. 각 셀의 값이 두 정수의 곱으로 이루어졌다는 힌트를 이용합니다.

낮은 수를 통해 규칙성을 찾아봅니다.

$2=1\times2$ : (1, 1)에서 (1, 2)는 오른쪽으로 1번 이동하면 됩니다.
$3=1\times3$ : (1, 1)에서 (1, 3)은 오른쪽으로 2번 이동하면 됩니다.
$4=1\times4$ : (1, 1)에서 (1, 4)는 오른쪽으로 3번 이동하면 됩니다.
그런데, 4는 1과 4의 곱도 되지만 2의 제곱으로도 표현할 수 있습니다.
$4=2\times2$ : (1, 1)에서 (2, 2)는 오른쪽으로 1번, 아래로 1번 총 2번 이동하면 됩니다.

좀 더 확장해서 테스트 예제를 보면 다음과 같습니다.

$10=1\times10=2\times5$ : (1, 1)에서 (1, 10)으로 이동하려면 총 9, (2, 5)로 이동하려면 총 5번 이동해야 합니다.
$50=1\times50=2\times25=5\times10$ : (1, 1)에서 (1, 50)으로 이동하려면 총 49, (2, 25)로 이동하려면 총 25, (5, 10)으로 이동하려면 총 13번 이동해야 합니다.

이를 통해 규칙을 찾아보면 다음과 같습니다.
1. $(1, 1)\rarr(x, y)$ 은 $(x-1)+(y-1)$번 이동해야 도달할 수 있습니다.
2. 최소한으로 이동하기 위해서는 $x+y\in \{x,y:x\times y=N\}$ 가 최소가 되어야 합니다.

따라서 정수 N을 입력받았을 때 $\text{divisor}(N) + N/(\text{divisor}(N))$가 최소가 될 때 그 값들의 합에 -2 한 것과 같습니다.

import java.util.Scanner;
import java.io.FileInputStream;
import java.lang.Math;

class Solution
{
    private static long solve(long number){
        long sqrtNumber = (long)(Math.sqrt(number));
        long count = number-1;
 
        for(long i=2;i<= sqrtNumber;i++){
            if(number % i == 0){
                count = Math.min(count, i + number/i - 2);
            }
        }
        return count;
    }
     
    public static void main(String args[]) throws Exception
    {
        Scanner sc = new Scanner(System.in);
        int T;
        long n;
        T=sc.nextInt();
 
        for(int test_case = 1; test_case <= T; test_case++)
        {
            n = sc.nextLong();
            System.out.println(String.format("#%d %d",test_case ,solve(n)));
        }
    }
}