[백준] 2609번 문제 풀이 - JAVA

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

 

풀이

---

해당 문제는 최대공약수와 최소공배수의 알고리즘 공식을 알면 쉽게 풀 수 있는 문제입니다.

최대공약수 :  두 수 이상의 여러 수의 공통된 최대 약수(약수 : 어떤 수를 나누어떨어지게 하는 수) 최소공배수 : 두 수 이상의 서로 공통으로 존재하는 배수 중 가장 작은 배수(배수 : 어떤 수 끼리 곱한 수)

 

최대공약수와 최소공배수를 구하는 수학 풀이를 보면 아래와 같습니다.

소인수분해

 

하지만 이렇게 나누고 구하면 수가 커질 경우 알고리즘을 작성하는 데 어려움이 발생합니다.

 

그래서 유클리드 호제법을 이용하면 됩니다.

 

유클리드 호제법( Euclidean algorithm )이란?

유클리드 알고리즘은 2개의 자연수 또는 정식(整式)의 최대공약수를 구하는 알고리즘의 하나

호제법이란,  두 수가 서로 상대방 수를 나누어서 결국 원하는 수를 얻는 알고리즘을 나타내는 것으로 명시적으로 기술된 가장 오래된 알고리즘 중 하나이다.

 

유클리드 호제법 - 위키백과, 우리 모두의 백과사전

2개의 자연수(또는 정식) a, b에 대해서 a를 b로 나눈 나머지를 r이라 하면(단, a>b), a와 b의 최대공약수는 b와 r의 최대공약수와 같다. 이 성질에 따라, b를 r로 나눈 나머지 r'를 구하고, 다시 r을 r'로 나눈 나머지를 구하는 과정을 반복하여 나머지가 0이 되었을 때 나누는 수가 a와 b의 최대공약수라고 한다.

 

위의 방법을 사용하면 아래와 같이 풀이를 할 수 있다.

 

최대공약수

24 와 18 을 나누었을 때, 나머지가 6이면 해당 나눈 수 18과 나머지를 나누었을 때 나머지가 0으로 나눠지면 

두 수의 최대 공약수는 6이다.

두 수의 나머지를 나눈 수에 나눴을 때 0이 된다면 해당 나머지는 최대공약수가 된다.

 

최소공배수

두 수의 곱했을 때, 해당 값을 구한 최대공약수로 나누게 된 수가 최소 공배수가 된다.

 

 

최대공약수만 구하면 해당 알고리즘은 쉽게 풀이되며 계속 0이 될 수 있는 나머지를 구하기 때문에 재귀 알고리즘을 적용해야된다.

 

코드

---

package Bronze;

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

public class B_2609 {

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer st = new StringTokenizer(br.readLine());
		
        // 두 수 입력 받음
        int num1 = Integer.parseInt(st.nextToken());
        int num2 = Integer.parseInt(st.nextToken());
    
        int gcd = getGCD(num1, num2); 
       
        //최대공약수 출력
        System.out.println(gcd);
        //최소공배수 출력
        System.out.println(((num1*num2)/gcd));
        
    }

	//최대공약수를 구하는 메서드
    private static int getGCD(int num1, int num2) {
       
        // 나머지가 0이면 return
        if (num1%num2 == 0) return num2;

		// 아닐 경우 다시 나눔
        return getGCD(num2, num1%num2);
    }
    
}