[programmers] 최소공배수와 최대공약수 (java) -1level

문제 설명

문제 해결

 

이 문제는 유클리드 호제법을 안다면 풀기 쉽다.

 

public class 최대공약수와최소공배수 {
    public int[] solution(int n, int m) {
        // n, m 최대공약수와 최소공배수 를 구해라.
        int[] answer = new int[2];
        int a = Math.max(n,m); // 둘 중에 더 큰 수
        int b = Math.min(n,m); // 둘 중에 더 작은 수

        while(b!=0){
            int r = a%b;
            a = b;
            b = r;
        }
        answer[0] = a;
        answer[1] = n * m / a; // 두 수를 곱하고 최대 공약수로 나눠주면 최소공배수

        return answer;
    }
}

 

유클리드 호제법이란?

 

두 정수 a, b 가 있을 때 (a가 b 보다 더 크다고 가정) a를 b로 나눈 나머지를 r이라 하자.

이때, a와 b의 최대공약수는 b와 r의 최대공약수와 같다.

반복문을 사용하여 r = 0 이 되면 두 정수의 최대공약수를 구할 수 있다.

 

최소공배수는 두 정수 a, b를 곱한 후 최대공약수로 나누어주면 구할 수 있다.