[프로그래머스(Java)] 피자 나눠 먹기 (2) / 유클리드 호재법

 

Level. 0

 

문제

머쓱이네 피자가게는 피자를 여섯 조각으로 잘라 줍니다.
피자를 나눠먹을 사람의 수 n이 매개변수로 주어질 때, n명이 주문한 피자를 남기지 않고 모두 같은 수의 피자 조각을 먹어야 한다면 최소 몇 판을 시켜야 하는지를 return 하도록 solution 함수를 완성해보세요.

* 제한사항
- 1 ≤ n ≤ 100

 

풀이

class Solution {
    
    int gcd(int a, int b){
        if(a%b==0) return b;
        return gcd(b, a%b);
    }
    
    public int solution(int n) {
        int answer = n/gcd(Math.max(n, 6), Math.min(n, 6));
        return answer;
    }
    
}

 

n과 6의 최소공배수(lcm = n1 * n2 / gcd)를 6으로 나눈 수를 구하는 문제이다. 

유클리드 호재법을 사용하여 최대공약수(gcd)를 구해 준 후

n * 6 / gcd / 6

즉 n / gcd 를 구하면 된다. 

 

 

---

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

프로그래머스