[백준] 2609 : 최대공약수와 최소공배수

 

 

처음엔 이렇게 풀었는데 특정 입력에서는 통하지 않아서 오답처리가 됐다.

import java.io.*;
import java.util.*;
public class Main{
    public static void main(String[] args)throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int A = Integer.parseInt(st.nextToken());
        int B = Integer.parseInt(st.nextToken());
        int GCD = 1, LCM = 1;
        
        while(true){
            if((A%2==0)&&(B%2==0)){
                A /= 2;
                B /= 2;
                GCD *= 2;
            }
            if((A%3==0)&&(B%3==0)){
                A /= 3;
                B /= 3;
                GCD *= 3;
            }
            if(!(((A%3==0)&&(B%3==0))||(A%2==0)&&(B%2==0))){
                LCM = GCD*A*B;
                break;
            }
        }
        
        System.out.println(GCD);
        System.out.println(LCM);
    }
}

 

 

그리고 이 포스트를 참고해서 다시 풀어봤다.

https://st-lab.tistory.com/154

[백준] 2609번 : 최대공약수와 최소공배수 - JAVA [자바]

 

짧게 요약하자면 숫자 A와 B가 있고, r을 A % B라고 했을 때 ( A >= B )

최대공약수 GCD(A,B) = GCD(B,r)이라는 것이다.

 

그리고 A = ad, B = bd (a와 b는 서로소이고, d는 A와 B의 최대공약수)라고 했을 때

A와 B의 최소공배수는 a*b*d이다.

 

따라서 A와 B가 주어지고 둘의 최대공약수인 d를 구한다면

A*B = a*d*b*d 이니 이것을 d로 나눠주면 최소공배수를 구할 수 있다.

 

 

import java.io.*;
import java.util.*;
public class Main{
    public static void main(String[] args) throws IOException{
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
        int A = Integer.parseInt(st.nextToken());
        int B = Integer.parseInt(st.nextToken());
        int d = gcd(A,B);
        
        System.out.println(d);
        System.out.println(A*B/d);
        
    }
    public static int gcd(int a, int b){
        while(b!=0){
            int r = a%b;
            a = b;
            b = r;
        }
        return a;
    }
    
    
}