[프로그래머스] 피자 나눠 먹기 (JAVA/ 자바)

 

 

풀이 코드

class Solution {
    public int solution(int n) {
        int answer = 0;
        int pizza = 6;
        int gcd = getGCD(pizza, n);
        
        answer = n / gcd;
        
        return answer;
    }
    
    public static int getGCD(int pizza, int n){
        if(n == 0){
            return pizza;
        }
        return getGCD(n, pizza%n);
    }
    
}

 

유클리드 호제법을 사용하여 해결하였다.

 

 

유클리드 호제법

 

두 수의 최대공약수를 구하는 알고리즘.

 

 

✅ 최대공약수(GCD)를 구할 경우

1. 재귀 방식

public static int getGCD(int a, int b){
	if(b == 0){
		return a;
	}
	return getGCD(b, a % b);
}

• b가 0일 경우에 a가 GCD가 됨.

 

2. 반복문(while) 방식

public static int getGCD(int a, int b){
	while (b != 0){
    	int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

 

 

 

✅ 최소공배수(LCM) 을 구할 경우

public static int getLCM(int a, int b){
	return a * b / getGCD(a, b);
}

• 두 수의 곱을 최대 공약수로 나누면 됨.