[알고리즘문제풀기]피자 나눠 먹기(2)

문제

나의 해답

class Solution { 
    public int solution(int n) { 
        int gcd = gcd(n, 6); 
        int lcm = (n * 6) / gcd;
        return lcm / 6; 
    }
    private int gcd(int a, int b) { 
        if (b == 0) { 
            return a; 
         } 
         return gcd(b, a % b); 
    }
}

해설

• 남기지 않고 모두 같은 수의 피자 조각을 먹어야 한다 - > 최소 공배수를 확인해야함

• 최소 공배수를 구하려면 두 수의 곱/최대 공약수

• 유클리드 호제법 알고리즘을 활용하여 최대 공약수 확인