[java] 백준 알고리즘 1934번 최소공배수 풀이 소스

난 문과에 비전공 출신이므로 수학을 싫어하진 않지만, 복잡한 공식을 잘 모르는 편이다.

최소공배수를 구하는 방법도 아래와 같은 방법 밖에 생각나지 않았다.

유클리드 호제법이라는 공식을 이용해 훨씬 빠른 코드를 만들어내시는 분들도 계셨지만, 

내가 아는 지식으로 해답을 찾기 위해 고민해서 해결했다. 

위에 올려둔 그림을 그대로 소스로 옮겨 놓으려고 애썼다. 

'컴퓨터가 인간처럼 대충 이 수가 들어가면 빠르겠다'같은 경우를 만들어주기 힘드니 숫자가 차례대로 올라가면서

나눠주는 방식으로 만들었다.

아래 풀이소스 *

 
public class Baekjoon1934 {
     
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        
        int t = Integer.parseInt(br.readLine()); // 테스트 케이스의 개수 
        String[] preInputArray = new String[2];
        int[] inputArray = new int[2]; // 비교할 A,B가 들어갈 배
        int[] leastCommonMultiple = new int[t]; // 테스트 케이스들의 최소공배수 배열 
        
        for(int i=0; i<t; i++) { // 테스트 케이스만큼 만들어냄. 
            preInputArray = br.readLine().split(" ");
            inputArray[0] = Integer.parseInt(preInputArray[0]); // 자연수 A
            inputArray[1] = Integer.parseInt(preInputArray[1]); // 자연수 B
            Arrays.sort(inputArray); 
            
            int smallInput = inputArray[0]; // A와B 중에 작은 값 
            int bigInput = inputArray[1]; // A와B 중에 큰 값  
            ArrayList<Integer> quetientArray = new ArrayList<>(); // 
            int resultQuetient = 1; // 그림에서 왼쪽에 나올 나누는 값들의 총 곱 
            int divide =1; // 나누는 수 
            
            while(divide <= inputArray[0]) { // 나누는 수가 주어진 작은 수를 넘어갈 수 없다. 
                float firstRemainder = smallInput%divide; // 작은 수를 나눈 뒤 나머지 
                float secondRemainder = bigInput%divide; // 큰 수를 나눈 뒤 나머지 
                
                if(firstRemainder == 0 && secondRemainder == 0) { // 둘 다 0이면 다음 단계로 넘어간다. 
                    quetientArray.add(divide); // 이렇게 그림 왼쪽에 나오는 몫들이 리스트에 담긴다. 
                    
                    smallInput = smallInput/divide; // 공약수로 나눠줬기 때문에 다음 단계로 넘어간다.
                    bigInput = bigInput/divide;
                    divide = 1; // 다음 단계로 넘어가면 다시 처음부터 나눠줘야하고 또 1로 나눠줄 필요 없기 때문에 1로 초기화하고 뒤에 ++로 2를 만들어준다.
                }
                divide++; // 나눠주는 수가 계속해서 올라간다.
                
            }
            
            for(int k=0; k<quetientArray.size(); k++) {
                resultQuetient = resultQuetient*quetientArray.get(k); // 최소공배수 구하기 그림에서 왼쪽의 몫들을 총 곱해준다.
            }
            
            leastCommonMultiple[i] = resultQuetient*smallInput*bigInput; // 그림 왼쪽 몫들의 총 곱 * 남은 수 * 남은 수는 최소공배수다 
            
        }
        
        for(int h=0; h<leastCommonMultiple.length; h++) {
            System.out.println(leastCommonMultiple[h]);
        }
        
 
    }
 
}