[Java] 피자 나눠먹기(2) _ 최소 공배수, 최대 공약수, 유클리드 호제법의 원리 사용

Problem 💻

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

프로그래머스

문제 설명

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

---

제한사항

1 ≤ n ≤ 100

입출력 예nresult

6	1
10	5
4	2

---

Approach 1 ❌ - 나의 초기 접근법

사실 어떻게 접근을 시작해야 할지도 떠오르지 않았다...

나의 수학적 사고체계의 미숙함이 드러난다.

수학 좀 열심히 할걸...

---

Approach 2 ⭕

이 문제를 해결하기 위해 최소공배수(LCM, Least Common Multiple) 의 개념을 사용하면 된다.

피자 한 판은 6조각으로 나누어지므로, 6과 n(사람 수)의 최소공배수를 구하면 된다.

 

논리적 전개

1. 문제 이해

피자 한 판은 6조각으로 나뉘어 있으며, n명이 모두 남김없이 같은 양의 조각을 먹어야 한다.

즉, 6과 n의 최소공배수를 구해야 한다.

 

2. 최소공배수(LCM) 활용

최소공배수는 두 수의 공통 배수 중 가장 작은 수를 의미한다.

예를 들어 n = 10일 때:

 • 피자 한 판당 조각 수 = 6

 • 사람 수 = 10

• 6과 10의 최소공배수는 30이므로, 30조각이 필요하다.

이때 피자 판 수는 30 ÷ 6 = 5판이 된다.

 

3. 피자 판 수 계산

최소공배수(LCM)를 피자 한 판당 조각 수인 6으로 나누면 필요한 피자 판 수를 구할 수 있다.

식으로 표현하면 다음과 같다.

 

= {LCM(6,n)} / 6

 

---

알고리즘 단계

1. 6과 n의 최대공약수(GCD) 를 구한다.

GCD를 구하면 최소공배수는 다음과 같이 계산할 수 있다.

 

최소 공배수(a, b) = (a * b) / {최대공약수}(a, b)}

 

여기서 a = 6, b = n이다.

 

GCD는 “Greatest Common Divisor” 의 약자로, 최대공약수를 의미한다.두 수의 공통된 약수 중 가장 큰 값이다.
반대로 LCM(Least Common Multiple)은 최소공배수로, 두 수의 공통된 배수 중 가장 작은 값을 의미한다.

LCM과 GCD의 관계

두 수 a와 b의 최소공배수(LCM)는 두 수의 곱을 최대공약수(GCD)로 나눈 값으로 구할 수 있다.
이 관계는 수학적으로 다음과 같다:

왜 이 식이 성립하는가?
• 두 수 a와 b의 곱은 두 수의 모든 공통 요소를 포함한다.
• 그러나 이때 공통된 약수(최대공약수)가 중복되기 때문에, GCD로 나누면 중복을 제거하고 최소공배수가 된다.

 

2. 구한 LCM을 6으로 나누어 피자 판 수를 계산한다.

---

Solution 💡

 

class Solution {
  public int solution(int n) {
     // 최대공약수(GCD)를 구하는 함수
     int gcd = gcd(6, n);
     
     // 최소공배수(LCM)를 구하고 피자 판 수 계산
     int lcm = (6 * n) / gcd;
     
     // 최소공배수를 피자 한 판당 조각 수(6)로 나눈 값이 필요한 피자 판 수
     return lcm / 6;
  }
  //유클리드 호제법으로 최대공약수(GCD)구하기
  public int gcd(int a, int b) {
      if (b == 0) return a;
      return gcd(b, a % b);
  }
}

 

코드 설명

1. 최대공약수(GCD) 는 gcd 함수를 통해 구한다.

  • 유클리드 호제법을 사용해 효율적으로 최대공약수를 구한다.

2. 최소공배수(LCM) 는 GCD를 이용해 계산한다:

 

3. 피자 판 수는 LCM을 6으로 나눈 값이 된다.

 

---

Reference 📄

유클리드 호제법은 다음 게시물에!