피자 나눠 먹기 (2)

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

 

🦛 제한사항

1 ≤ n ≤ 100

🦛 입출력 예

n	result
6	1
10	5
4	2

 

🦛 입출력 예 설명

 

입출력 예 #1

• 6명이 모두 같은 양을 먹기 위해 한 판을 시켜야 피자가 6조각으로 모두 한 조각씩 먹을 수 있습니다.

입출력 예 #2

• 10명이 모두 같은 양을 먹기 위해 최소 5판을 시켜야 피자가 30조각으로 모두 세 조각씩 먹을 수 있습니다.

입출력 예 #3

• 4명이 모두 같은 양을 먹기 위해 최소 2판을 시키면 피자가 12조각으로 모두 세 조각씩 먹을 수 있습니다.

🦛 풀이

🍕 문제 핵심 요약

• 피자 한 판은 6조각.
• 사람 수 n이 주어졌을 때,
• n명이 피자를 똑같이 나눠먹고, 남김없이 먹기 위해
• 몇 판의 피자를 최소로 시켜야 하는가?
  
  

🧠 접근 방법

1. 공통 분배 가능한 조각 수 찾기

• 한 판에 6조각이니까, 총 조각 수가 6 * x가 될 거야 (x는 판 수).
• 이 조각 수가 n으로 나누어떨어져야 각자 똑같이 나눠먹을 수 있다.

즉, 6 * x % n == 0을 만족하는 최소의 x를 찾아야 한다.

2. 최소 공배수 개념 도입

• 위 문제를 잘 보면,
• 6 * x가 n의 배수여야 한다 →
  즉, 6과 n의 최소공배수를 먼저 구하고
  그 최소공배수를 6으로 나누면 시켜야 할 판 수가 나온다.

📦 요약 단계

1. LCM(6, n)을 구한다.
2. 그 결과를 6으로 나눈다.
3. 결과가 피자 판 수이다.
   
   

🔧 참고 개념: LCM(최소공배수) 구하는 방법

• LCM(a, b) = (a * b) / GCD(a, b)
• GCD는 두 수의 최대공약수 (유클리드 알고리즘 사용 가능)
  
  

✅ 유클리드 알고리즘 설명

• GCD(a, b)는 b가 0이 될 때까지 a % b를 반복하는 방식으로 구한다.
• 반복적으로 a = b, b = a % b를 수행.
  
  

✍️ Java로 GCD(최대공약수) 함수 만드는 방법

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

🔚 결론

class Solution {
    public int solution(int n) {
        int a = 6;
        int b = n;
        
        // 유클리드 알고리즘으로 GCD 구하기
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        
        // 최소 피자 판 수 = n / GCD(6,n)
        int answer = n / a;
        return answer;
        
    }
}