[백준 알고리즘/Java] 2609 최대공약수와 최소공배수

문제이해

2개의 수를 입력받고 for문으로 1부터 증가하면서 2개의 수가 동시에 나머지가 0인 구간은 최대공약수로 생각했고

2개의 수중 작은 수를 시작으로 1부터 곱해가면서 그 결과가 동시에 나머지가 0이 나올 때까지 반복하겠다고 생각했습니다.

 

코드

public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringBuilder sb = new StringBuilder();

        String[] Num = br.readLine().split(" ");
        int num1 = Integer.parseInt(Num[0]);
        int num2 = Integer.parseInt(Num[1]);


        //최대공약수
        if(num1 > num2){
            for(int i = num2; i > 0; i--){
                if((num1 % i) == 0 && (num2 % i) == 0 ){
                    sb.append(i);
                    sb.append("\n");
                    break;
                }
            }
        }else{
            for(int i = num1; i > 0; i--){
                if((num1 % i) == 0 && (num2 % i) == 0 ){
                    sb.append(i);
                    sb.append("\n");
                    break;
                }
            }
        }

        //최소공배수
        if(num1 > num2){
            for(int i = 1; i < num1; i++){
                int result = num2 * i;
                if((result % num1) == 0 && (result % num2) == 0 ){
                    sb.append(result);
                    break;
                }
            }
        }else{
            for(int i = 1; i < num2; i++){
                int result = num1 * i;
                if((result % num1) == 0 && (result % num2) == 0 ){
                    sb.append(result);
                    break;
                }
            }
        }
        System.out.println(sb);
    }

이렇게 했는데 오답이 나왔습니다. 

보면 num1,num2중에서 num1을 큰값으로 설정하고 swap해주는 과정이 있었으면 더 짧아졌을거 같습니다.

접근을 잘못했다고 판단해서 다른 풀이를 찾아봤습니다.

 

코드

public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] Num = br.readLine().split(" ");
        int num1 = Integer.parseInt(Num[0]);
        int num2 = Integer.parseInt(Num[1]);
        
        int result = num1 * num2;

        if(num1 < num2){
            int temp;
            temp = num1;
            num1 = num2;
            num2 = temp;
        }

        //최대공약수 - 유클리드 호제법(num2의 나머지가 0보다 크면 나머지를 나누기)
        //1. a = 10, b = 8, 나머지 2 => a = 8, b = 2
        //2. a = 8, b = 2, 나머지 0 => a = 2, b = 0
        while(!(num1 % num2 == 0)){
            int temp = num2;
            num2 = (num1 % num2);
            num1 = temp;
        }
        System.out.println(num2);

        //최소공배수 - 두 수의곱 / 최대공약수
        System.out.println(result / num2);

    }

유클리드 호제법이라는게 있었습니다. 최대공약수를 쉽게 구하게해줍니다. 나머지가 0이 나올 때 까지 수를 바꿔가면서 구하는 것입니다. 

최소공배수도 공식이 있었습니다. 두수의 곱을 최대공약수로 나누면 됩니다.