피자 나뉘 먹기(2) ★최소공배수, 최대공약수★

나의 풀이 

class Solution {
     public int solution(int n) {
        int big=Math.max(6,n);
        int gop=6*n;
        int result = 0;
        if(n==1){
            return 1;
        } else{
            for(int i=big; i<=gop; i++){
                if(i % 6 ==0 & i % n==0){
                    result=i/6;
                    break;
                }
            }
            return result;
        }
       
    }

}

 

 

다른 사람의 풀이 

class Solution {
    public int GCD(int num1, int num2) {
        if (num1 % num2 == 0)
            return num2;
        return GCD(num2, num1 % num2);
    }

    public int LCM(int num1, int num2) {
        return num1 * num2 / GCD(num1, num2);
    }

    public int solution(int n) {
        return LCM(n, 6) / 6; //최소공배수를 6으로 나누어야 피자 판 수가 나온다.
    }
}

▶ 두 수의 곱을 최대공약수로 나누면,  최소공배수가 나온다.

 

▶ 최대공약수를 구하는 논리

     num1 = 10     num2 =6

     num1 % num2 = 10 % 6 =4   ≠ 0

 

     num2 = 6

     num1 % num2 =4

---

    

     num1 = 6

     num2 = 4

     num1 % num2 = 6 % 4 = 2  ≠  0

    

     num2 =4

     num1 % num2 =2

 

---

 

     num1 = 4

     num2 = 2

     num1 % num2 = 4 % 2 ==0

     return num2

 

     ※ 10과 6의 최대 공약수는 2이다.