피자 나눠 먹기 (2)

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

프로그래머스

---

문제 설명
머쓱이네 피자가게는 피자를 여섯 조각으로 잘라 줍니다. 피자를 나눠먹을 사람의 수 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조각으로 모두 세 조각씩 먹을 수 있습니다.

---

문제를 잘 살펴보면 다음과 같은 정보를 얻을 수 있습니다.

1. 피자는 항상 여섯 조각으로 잘린다.

2. 피자는 남기면 안된다. 즉, 나머지가 없어야 한다.

3. n명은 피자를 같은 양으로 먹어야 한다.

 

감이 오시나요? 그렇습니다. 최소공배수 문제입니다.

최소공배수는 math 패키지의 lcm 함수로 사용할 수 있지만, 파이썬 3.9 버전 이상부터 지원하는 기능입니다.

이번엔 최대공배수인 gcd를 사용해서 문제를 풀어보도록 하겠습니다.

 

최소공배수는 생각보다 간단한 공식이 있습니다.

숫자 a, b가 주어졌을 때, lcm(a, b) = a * b / gcd(a, b)입니다.

 

파이썬으로 이 공식을 구현하여 풀겠습니다.

import math
def solution(n):
    answer = n / math.gcd(n , 6)
    return answer

 

한 판당 여섯 조각이므로, answer * 6이 총 조각입니다.

answer * 6 => n과 6의 최소공배수이므로, answer * 6 = n * 6 / math.gcd(n, 6)이니, 각 식에서 *6을 제거해줄 수 있습니다.

최종적으로 식은 answer = n / math.gcd(n, 6)이 됩니다.

 

최소공배수 문제는 lcm을 쓸 수 있는 버전과 아닌 버전이 나뉘므로, 두 수의 곱을 최대공약수로 나눠서 얻는 방법도 알아두시길 바랍니다.