[Programmers] Lv.0 | 피자 나눠 먹기 (2) | Java

문제

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

 

풀이

class Solution {
    public int solution(int n) {
        int pizza = 1;
        
        while ((6 * pizza) % n != 0) {
            pizza++;
        }
        
        return pizza;
    }
}

class Solution {
    public int solution(int n) {
        return (6 * n / gcd(6, n)) / 6;
    }

    private int gcd(int a, int b) {
        return b == 0 ? a : gcd(b, a % b);
    }
}

• gcd(6, n) → 6과 n의 최대공약수 계산
• 6 * n / gcd(6, n) → 최소공배수 계산
  LCM(6, n) = (6 × n) ÷ GCD(6, n)
• (LCM(6, n)) / 6 → 최소 피자 판 수 계산
  총 조각 ÷ 한 판 조각 수 = 최소 판 수

---

최소공배수(LCM)와 최대공약수(GCD) 완전 정리

1. 최대공약수(GCD, Greatest Common Divisor)

정의

• 두 수의 공통된 약수 중 가장 큰 수를 최대공약수라고 함

예제

• 6과 10의 최대공약수?
  • 6의 약수: 1, 2, 3, 6
  • 10의 약수: 1, 2, 5, 10
  • 공통 약수: 1, 2 → 최대공약수 = 2

공식

• 유클리드 호제법(Euclidean Algorithm)을 사용하면 쉽게 구할 수 있음

유클리드 호제법 원리

• 두 수 a, b(a > b)에 대해
  GCD(a, b) = GCD(b, a % b)
• 나머지가 0이 될 때, 나누는 수가 최대공약수

예제 계산: GCD(6, 10)

1. GCD(10, 6) → 10 % 6 = 4 → GCD(6, 4)
2. GCD(6, 4) → 6 % 4 = 2 → GCD(4, 2)
3. GCD(4, 2) → 4 % 2 = 0 → GCD = 2

 

2. 최소공배수(LCM, Least Common Multiple)

정의

• 두 수의 공통된 배수 중 가장 작은 수를 최소공배수라고 함

예제

• 6과 10의 최소공배수?
  • 6의 배수: 6, 12, 18, 24, 30, 36, …
  • 10의 배수: 10, 20, 30, 40, 50, …
  • 공통 배수 중 가장 작은 수 = 30 → LCM(6, 10) = 30

공식

• 최대공약수(GCD)를 이용해서 구할 수 있음
• LCM(a, b) = (a × b) / GCD(a, b)
• 이 공식은 두 수의 곱에서 겹치는 부분(GCD)을 나누어 최소 공배수를 구하는 원리

 

3. 유클리드 호제법 정리

핵심 원리

• 두 수 a, b에 대해 GCD(a, b) = GCD(b, a % b)
• 반복/재귀로 나머지가 0이 될 때까지 계산

손으로 계산 예제

• GCD(48, 18)
  1. 48 % 18 = 12 → GCD(18, 12)
  2. 18 % 12 = 6 → GCD(12, 6)
  3. 12 % 6 = 0 → GCD = 6

 

4. 피자 문제 적용

• 한 판 피자 = 6조각
• 사람 수 = n명
• 조건: 남기지 않고 똑같이 나눠야 함

논리

1. 총 피자 조각 수 = 6 × 판 수
2. 6 × 판 수가 n으로 나눠떨어져야 함
3. 최소 총 조각 수 = LCM(6, n)
4. 따라서 최소 판 수 = LCM(6, n) ÷ 6

 

5. 예제

n	LCM(6, n)	최소 판 수
6	6	1
10	30	5
4	12	2

 

6. 최종 코드 (메서드 분리 없이 깔끔하게)

class Solution {
    public int solution(int n) {
        int a = 6, b = n;

        // GCD 계산 (유클리드 호제법)
        while (b != 0) {
            int temp = b;
            b = a % b;
            a = temp;
        }
        int gcd = a;

        // 최소공배수 계산
        int lcm = 6 * n / gcd;

        // 피자 판 수 계산
        return lcm / 6;
    }
}

설명

1. while문 → GCD 계산
2. 6 * n / gcd → 최소공배수 계산
3. lcm / 6 → 판 수 계산