[SWEA / 구구단 걷기 / JAVA]

https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AYaf9W8afyMDFAQ9 

SW Expert Academy

 

문제 접근

구하고자하는 수의 제곱근을 기준으로 약수는 대칭성을 가지고 있다 

16의 약수는 1, 2, 4, 8 ,16이며 제곱근은 4이다. 4를 기준으로 양 옆 한 칸씩 곱해보면 16이 되는 걸 알 수 있다.

→ 2 * 8, 1 * 16

그래서 배열을 제곱근까지 돌려서 약수를 찾고 N / 약수를 하면 대칭되는 약수도 같이 찾을 수 있다.

 

처음엔 약수를 구한 후 약수의 배열을 만들어서 제곱근 양 옆에 있는 인덱스들을 곱하는 방식으로 접근했으나 테스트 케이스 몇 개가 맞지 않았다.

양 옆 인덱스들이 최소 횟수가 아니었나보다.

그래서 Math.min()으로 약수들을 구한 뒤 어느쪽이 최소인지 매 번 검사 

 

import java.util.*;
import java.io.*;

public class Solution {
	static long N;
    
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		
		int T = sc.nextInt(); // 테케
		
		for(int t=1; t<=T; t++) {
			 N = sc.nextLong();
			
			count(t);
		}
	}
    
	private static void count(int t) {
		long left = 0;
		long right = 0;
		long result = Long.MAX_VALUE;
		
		for(long i=1; i<=Math.sqrt(N); i++) {
			if(N % i == 0) {
				left = i-1;
				right = N / i-1;
				result = Math.min(result, left+right);
			}
		}
		System.out.println("#"+t+" " + result);
	}
}