[백준] 1934번 최소공배수 JAVA (자바) 풀이

문제 1934번

 

 [입력]

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

 [출력]

 :  첫째 줄에는 테스트 케이스의 개수 

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

 

 [팁]

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

 

  <유클리드 호제법>

  - 최대공약수 = 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));
        int T = Integer.parseInt(br.readLine());
       
        for(int i =0; i<T;i++){
            StringTokenizer st = new StringTokenizer(br.readLine());
            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());
            int G = gcd(A,B);
            int L = A*B/G;
            System.out.println(L);
        }
    }
    public static int gcd(int A, int B){
        if(B==0)
            return A;
        else
            return gcd(B,A%B);
    }
}

 

 [해설]
     

 :  int T = Integer.parseInt(br.readLine());  첫째줄 입력

 

 :  for(int i=0; i<T; i++){  StringTokenizer 부터는 for 문에 넣어야 돌아간다
         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);  최대공약수

         int L = A*B/G;  최소공배수
         System.out.println(L);  최소공배수 출력

   }

 :  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/1934

1934번: 최소공배수

 

 

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