[백준] 2609번 최대공약수와 최소공배수 JAVA (자바) 풀이

문제 2609번

 

 [입력]

 :  첫째 줄에는 두 개의 자연수

 [출력]

 :  첫째 줄에는 두 수의 최대공약수 출력

    둘째 줄에는 두 수의 최소 공배수 출력

 

 [팁]

 :  최대공약수와 최소공배수는 유클리드 호제법을 이용한다

 

  <유클리드 호제법>

  - 최대공약수 = GCD

  -  A와 B의 최대공약수를 (A,B)라고 할 때 최대공약수 (B,R)의 최대공약수와 같다

  -  A, B ∋ ℤ  ( A ≥ B )

  -  R = A를 B로 나눈 나머지

  -  GCD(A,B) = GCD(B,R)

 

  - 최소공배수 = LCM

  - A와 B의 최소공배수는 GCD × (A/GCD) × (B/GCD) = (A×B) / GCD

 

 

 [코드]

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 G = gcd(A,B);
        
        System.out.println(G);
        System.out.println(A*B/G);    
    }
    
    public static int gcd (int A, int B){
        if(B==0)
            return A;
        else
            return gcd(B,A%B);   
    }
}

 

 [해설]
     

 :  StringTokenizer st = new StringTokenizer(br.readLine());  첫번째 입력줄을 공백단위로 읽어온다
        
 :  int A = Integer.parseInt(st.nextToken());  입력 받은 숫자 A, B
    int B = Integer.parseInt(st.nextToken());

 

 :  int G = gcd(A,B);  최대공약수
        
 :  System.out.println(G);  최대공약수 출력
 :  System.out.println(A*B/G);  최소공배수 출력
     
 :  public static int gcd (int A, int B){  매번 갱신되는 gcd 정의 
        if(B==0)
            return A;  B값이 0이 되면 A 호출 ( = A가 최대공약수 G가 된다 )
        else
            return gcd(B,A%B);  B값이 0이 아니라면 B를 (A자리)로 데려오고  
    }                                        A를 B로 나눈 나머지를 (B자리)에 대입
   
       

 

이제 풀어보러 갈께요 :)

 

 

https://www.acmicpc.net/problem/2609

2609번: 최대공약수와 최소공배수

 

 

* 독학으로 익히는 코딩이라 틀린 것이 있을 수 있습니다. 오류가 있다면 댓글을 통해 알려주세요. 감사합니다. *