코드업 1092 최소공배수(LCM), 최대공약수(GCD)

1092문제

서로다른 3명의 학생이 같은 날에 가입했고 그 다음부터 규칙적으로 코드업 사이트에 출석을한다 하지만 서로 규칙적으로 출석하는 날이 다르다

이때 3명이 같이 출석하는 날은 가입후 몇일뒤인가?

1번학생은 3일마다 한번 출석
2번학생은 5일마다 한번 출석
3번학생은 9일마낟 한번 출석

이러면 누구나 생각하는데 최소공배수를 떠올린다
하지만 나는 그 전에 무한 while문을 돌면서 count를 ++한다음
그 안에서 if문을 통해 3,5,9랑 나눌때 나머지가 0인 날을 구하는 코드를 짰다

하지만 이 코드는 너무 비효율적이기때문에 최소공배수를 써야했다
최소공배수를 구하는 방법으로 각 수가 나뉘어지지 않을때까지(소수) 나눈다음 그 수들을 곱하는 방식으로 코드를 짰지만 이 방법도 비효율적이었다

그래서 검색을 해 보았더니 '유클리드 호제법'이라는 방법이 있어서 여기에 적어본다

유클리드 호제법

유클리드 호제법 :두 수의 최대공약수를 구하는 알고리즘이다

찾은바로는 세상에서 제일 오래된 알고리즘이라는데.. 모르겠다

방법

1. num1%num2 계산을 하고 나온 값을 gcd라고 한자
2. num2%gcd 계산을 한다 여기서 나온값을 gcd2라고 하자
3. gcd%gcd2 계산을한다
4. 나머지가 0이 될때까지 위의 함수를 무한반복(재귀)을하고 0이 나오면 오른쪽 피연산자를 리턴한다

이렇게 나온 gcd가 최대공약수가 되게된다

코드

public static void main(String[] args) {
	//9과 3의 최대공약수
    int num = getGCD(9,3);
    // -> 3
}

public static int getGCD(int num1, int num2) {
        if (num1 % num2 == 0) {
            return num2;
        }
        return getGCD(num2, num1%num2);
    }

위에 코드를 보면 알 수 있듯이 return에서 자기 자신을 호출하면서 인수를 num1자리에 num2를주고 num2자리에 num1%num2를 해서 나온 나머지를 넣었다.

그리고 if문에서 나머지가 0일경우 num2를 리턴시켰다.

이제 여기서 최소공배수를 구하는건 쉽다

두 수를 곱한다음 최대공약수랑 나누어주면 최소공배수가 된다

int num = getGCD(9,3);
int lcm = (9*3)/num;
// -> 9

이제 세 수의 최소공배수를 구하려면 어떻게 할까
당연히 두 수의 최소공배수를 구하고 나온 결과랑 남은 수랑 비교하면 세 수의 최소공배수가 나온다. 그래서 나온 코드업 1092의 코드는 아래와 같다

import java.util.Scanner;

public class CodeUp_1092 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        int n1 = sc.nextInt();
        int n2 = sc.nextInt();
        int n3 = sc.nextInt();

        int[] arr = {n1,n2,n3};

        int result1 = n1*n2/getGCD(n1,n2);
        int result2 = result1*n3/getGCD(result1,n3);

        System.out.println(result2);
    }

    public static int getGCD(int num1, int num2) {
        if (num1 % num2 == 0) {
            return num2;
        }
        return getGCD(num2, num1%num2);
    }
}