[BOJ] 2609 _ Java

📝 Problem

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

시간 제한	메모리 제한
1초	128 MB

문제

두 개의 자연수를 입력받아 최대 공약수와 최소 공배수를 출력하는 프로그램을 작성하시오.

입력

첫째 줄에는 두 개의 자연수가 주어진다. 이 둘은 10,000이하의 자연수이며 사이에 한 칸의 공백이 주어진다.

출력

첫째 줄에는 입력으로 주어진 두 수의 최대공약수를, 둘째 줄에는 입력으로 주어진 두 수의 최소 공배수를 출력한다.

---

최대공약수와 관련하여 '유클리드 호제법'을 들어본 적이 있다.

해당 문제를 해결하기 전, 유클리드 호제법부터 학습하였다.

---

🔍 Learn & Solution

- Learn

   유클리드 호제법(= 유클리드 알고리즘)

유클리드 호제법은 두 수의 최대공약수를 구하는 알고리즘으로, 시간복잡도는 O(log n)이다. 호제법은 두 수가 서로 상대방 수를 나누어 원하는 수를 얻는 것을 말한다.

두 수 a, b (a>b) 에 대하여 a % b = r 이라고 할 때,
a와 b의 최대공약수는 b와 r의 최대공약수와 같다.

이에 따라, b를 r로 나눈 나머지 r'을 구하고, r을 r'으로 나누는 과정을 반복하는데, 나머지가 0이 되었을 때, 나누는 수가 a와 b의 최대공약수가 된다.

첫 번째 반복) b를 a, r을 b라고 생각하자. b % r = r'라고 할 수 있고, b와 r의 최대공약수는 r과 r'의 최대공약수가 되는 것이다.

📌 알고리즘

1. 입력으로 두 수 a, b(a>b)를 받는다.
2. a가 b로 나누어 떨어지면, b을 출력하고 알고리즘을 종료한다.
   - b가 0이라면, a을 출력하고 알고리즘을 종료한다.
3. a가 b로 나누어 떨어지지 않으면, a에 b를, b에 a를 b로 나눈 나머지를 대입하여, 2번으로 돌아온다.
   
   
   

- Solution : 최대공약수(G)와 최소공배수(L) 출력

1. [1.~3.] 유클리드 호제법으로 최대공약수 구하기
2. [4.] 최대공약수와 최소공배수의 관계를 이용하여 최소공배수 구하기
   
   

1. 입력으로 두 수 a, b(a>b)를 받는다.

공백을 기준으로 두 수를 입력받고, 둘 중 큰 수를 a에, 작은 수를 b에 저장한다.

2. a가 b로 나누어 떨어지면, b을 출력하고 유클리드 알고리즘을 종료한다.

a가 b로 나누어 떨어지면, b가 a의 최대공약수 G이다.

3. ★ a가 b로 나누어 떨어지지 않으면, a에 b를, b에 a를 b로 나눈 나머지를 대입하여, 2번으로 돌아온다. (a=b, b=a%b)

a를 b로 나누어 나머지가 0이 될 때까지 과정을 반복한다.
* 재귀함수, for문 모두 가능

4. 최소공배수 L을 연산하여 출력한다.

• L = a x b / G

최소공배수는 입력받은 두 수의 곱을 최대공약수로 나눈 값과 같다.

---

💻 Code

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class BJ_2609 {
  public static int gcd(int a, int b){
      if(b==0)
          return a;
      while(true){
          int x = a%b;
          if (x==0)
              return b;
          else{
              int temp = b;
              b = a%b;
              a = temp;
          }
      }
  }

  public static void main(String[] args) throws IOException {
      BufferedReader bf = new BufferedReader(new InputStreamReader(System.in));
      StringTokenizer st = new StringTokenizer(bf.readLine());
      int a, b, result;

      a = Integer.parseInt(st.nextToken());
      b = Integer.parseInt(st.nextToken());

      if(a<b) {
          int temp = a;
          a = b;
          b = temp;
      }

      result = gcd(a, b);
      System.out.println(result);
      System.out.print(a*b/result);
  }
}