[백준 1934] 최소공배수 (JAVA)

백준 1934번 문제  - 최소공배수

1934번: 최소공배수

---

문제 분석

 

 

• 두 자연수를 입력 받아, 최소 공배수를 출력해라.

---

해결 키 포인트

 

• 유클리드 호제법을 이용해 최대 공약수를 알아낸다
• 알아낸 최대 공약수를 통해 최소 공배수 구하기
  • 최소 공배수 = 최대 공약수 * (A/최대 공약수) * (B/최대 공약수)

---

유클리드 호제법

MOD연산을 이용해 두 수의 최대 공약수를 구하는 알고리즘이다.

 

MOD 연산 :  두 값을 나눈 나머지를 구하는 연산
ex. 10 MOD 4 = 2 (10 % 4 = 2)

 

유클리드 호제법 알고리즘

 

1. 큰 수를 작은 수로 나누는 MOD 연산 수행

2. 앞 단계에서의 작은 수와 MOD 연산 결과 값(나머지)으로 MOD 연산 수행

3. 나머지가 0이 되는 순간의 작은 수를 최대 공약수로 선택

 

Do It! 알고리즘 코딩 테스트 기본

---

코드

import java.io.*;
import java.util.StringTokenizer;

public class Main {
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out));

        // N 입력
        int N = Integer.parseInt(br.readLine());

        // N번 반복
        for(int i=0;i<N;i++) {
            // 두 수 입력
            StringTokenizer st = new StringTokenizer(br.readLine());
            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());

            // 최소 공약수 구하기
            int sum = (A>=B) ? A%B : B%A;
            int gcd = (A<B) ? A : B;
            while(sum > 0) {
                int temp = sum;
                sum = gcd % sum;
                gcd = temp;
            }

            // 최소 공약수를 가지고 최대 공배수 구하기
            int result = (A/gcd) * (B/gcd) * gcd;
            // 출력
            bw.write( result+ "\n");
        }
        bw.flush();
        bw.close();
    }
}