코딩테스트입문 > 피자 나눠 먹기 (2) - java # 유클리드 호제법

 

 

 

https://school.programmers.co.kr/learn/courses/30/lessons/120815

프로그래머스

 

 

 

---

 

 

class Solution {

    int gcd(int n, int m) {
        int r;
        if(n < m) {
            int temp = n;
            n = m;
            m = temp;
        }
        while(m > 0) {
            r = n % m;
            n = m;
            m = r;
        }
        return n;
    }

    public int solution(int m) {
        int answer = 0;
        int[] result = new int[2];

        if(m%6==0){
            answer = m/6; 
        }else{

            result[0] = gcd(6,m);
            result[1] = 6*m / result[0];   // 최소 공배수 
 
            answer = result[1] / 6;
        }
        return answer;
    }
}

 

 

---

 

최대 공약수와 최소 공배수를 구해서 해결한 문제

 

 

유클리드 호제법 - 최대공약수 구하는 함수 

 

 

 

class Solution {

    int gcd(int n, int m) {
        int r;
        
        // 더 큰수를 n 으로 두고 진행 -> ( a > b ) 조건 만족시키기 위함
        if(n < m) { 
            int temp = n;
            n = m;
            m = temp;
        }
        
        while(m > 0) {
            r = n % m;
            n = m;
            m = r;
        }
        return n;
    }

}