피자나눠먹기2(최소공배수 공식 꼭 암기!!!)

내풀이

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

    public static int lcm(int a, int b){
        return a*b / gcd(a,b);
    }
}

인원수 n과 피자조각 6 의 최소공배수를 풀어서 6으로 나누면 피자수가 나온다.

최대공약수(GCD, Greatest Common Divisor)란?
두 개 이상의 수에서 공통된 약수 중 가장 큰 값을 의미합니다.

예제 : 24와 36의 최대공약수 구하기

• 24의 약수: 1, 2, 3, 4, 6, 8, 12, 24
• 36의 약수: 1, 2, 3, 4, 6, 9, 12, 18, 36
• 공통된 약수: 1, 2, 3, 4, 6, 12
• 최대공약수(GCD) = 12

유클리드 호제법을 이용한 최대공약수 구하기

최대공약수는 유클리드 호제법을 이용하여 구할 수 있는데, 이는 큰 수를 작은 수로 나눈 나머지를 반복적으로 취하여 나머지가 0이 될 때 까지 작동하여 구하는 방식이다.

최대공약수 구하는 아래코드 반드시 암기!!!!!!!!!!!

// 재귀 방식
public static int gcd(int a, int b) {
    if (b == 0) return a;
    return gcd(b, a % b);
}

최소공배수(LCM, Least Common Multiple)란?
두 개 이상의 자연수의 공통 배수 중에서 가장 작은 수를 의미합니다.

예제 : 6과 8의 최소공배수

• 6의 배수: 6, 12, 18, 24, 30, 36, 42, ...
• 8의 배수: 8, 16, 24, 32, 40, 48, ...
• 공통 배수: 24, 48, 72, ...
• 최소공배수: 24 ✅

최소공배수 구하는 아래코드 반드시 암기!!!!!!!!!

// 최소공배수(LCM) 구하기
    public static int lcm(int a, int b) {
        return (a * b) / gcd(a, b);
    }