SWEA 16800. 구구단 걷기

행렬의 셀에 (i, j)의 위치에 ixj가 적혀있다. 현재 (1, 1) 에서 n이 적힌 셀까지 (i+1, j), (i, j+1) 이 두 가지 방법으로만 이동할 수 있을 때 이동 횟수의 최솟값을 구하는 문제이다.

 

n의 약수들 중에서 약수 + (n / 약수) 가 최소가 되게 하면 되며 이는 1부터 √(n) 까지 약수 중 가장 큰 약수로 계산했을 때 최소가 된다.

long dividor = -1;
for(long i=1; i<=Math.sqrt(n); i++) {
    if(n % i == 0) {
        dividor = i;
    }
}
sb.append(dividor -1 + n/dividor - 1).append('\n');

 

 

결과 코드는 다음과 같다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Solution {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int T = Integer.parseInt(br.readLine());
        StringBuilder sb = new StringBuilder();

        for (int tc = 1; tc <= T; tc++) {
            sb.append('#').append(tc).append(' ');
            long n = Long.parseLong(br.readLine());
            long dividor = -1;
            for(long i=1; i<=Math.sqrt(n); i++) {
                if(n % i == 0) {
                    dividor = i;
                }
            }
            sb.append(dividor -1 + n/dividor - 1).append('\n');
        }
        
        br.close();
        System.out.print(sb);
    }
}