[Lv.0] 피자 나눠 먹기(2)

---

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

 

해당 문제는 사람수 n과 피자 한판의 조각수인 6을 이용해 최소공배수와 최대공약수 를 구해서 풀면 된다.

유클리트 호제법(Euclidean Algorithm)을 이용해 최소공배수와 최대공약수를 구할 것이다.

 

우선 삼항연산{(조건문)? 참:거짓} 을 이용해 사람수 n과 피자 한판의 조각수인 6중 가장 큰 값을 변수명 larger에 저장한다.

최대공약수를 구하기 위한 변수명 gcd를 선언하고 정수 1부터 larger까지 반복문을 실행한다.

유클리드 호제법에서 최소공배수(LCM)를 구하는 공식은 LCM = a*b/최대공약수(GCD) 이다.

이제 최소공배수(=인원n이 똑같은 피자개수를 먹기위해 필요한 피자조각수)를 구했으니

피자를 최소 몇 판을 시켜야하는지 구해야한다. 피자 한 판에 6조각이니 구한 최소공배수/6을 리턴해주면 된다.

 

class Solution {
    public int solution(int n) {
        int answer = 0;
        int larger = (n<6)?6:n;
        int gcd = 0;
        
            for(int i = 1; i<=larger; i++){
                if(n%i==0&&6%i==0){
                    gcd = i;
                }
            }    
            answer = (n*6/gcd)/6;
        
        return answer;
    }
}

 

참조블로그 :

유클리트호제법