[백준] 2609번 최대공약수와 최소공배수

유클리드 호제법을 안다면, 쉽게 풀 수 있다!

GCD 최대공약수를 구하는 것이고

LCM 최소공배수를 구하는 것이다.

 

GCD는 2개의 방법이 있다.

// while문을 사용하는 방법
static int getGCD(int x, int y) {
    while(y != 0) {
        int temp = x % y;
        x = y;
        y = temp;
    }
    return x;
}

이 방버은 y가 0이 아니면 계속해서 반복하게 된다.

y로 x를 나눈 나머지가 temp에 저장되고

y는 x로 치환된다.

그리고 나머지 값은 y로 치환된다.

 

즉, 나머지가 되는 수로 계속 나누는 것이다.

// 재귀를 통해 푸는 방법
public static int getGCD(int num1, int num2) {
        if (num1 % num2 == 0) {
            return num2;
        }
    return getGCD(num2, num1 % num2);
}

 

이거는 나머지가 0이 되면 return해버리고

그게 아니면 나머지값으로 num2를 나누게 된다.