2024.11.29 math함수 없이 문제 풀기

[ 문제 - 피자 나눠 먹기 (2) ]

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

 

---

[ 제출한 정답 ]

def gcd(a, b):
    while b:
        a, b = b, a % b
    return a

def lcm(a, b):
    return a * b // gcd(a, b)

def solution(n):
    return lcm(6, n) // 6

---

 

문제 해설

문제 이해하기

머쓱이네 피자 가게에서 피자는 6조각으로 나뉩니다.
n명이 피자를 먹으려면, 모두 같은 조각 수를 먹어야 하고 피자가 남으면 안 돼요.

그럼, 최소 몇 판의 피자가 필요한지 알아보자.

• 최대공약수는 두 친구가 공통으로 먹을 수 있는 음식의 "크기"를 구하는 것.
• 최소공배수는 "필요한 총 양"을 계산하는 것.
• 피자를 나눌 때 남기지 않으려면 최소공배수만큼 조각이 필요하고, 이를 6조각씩 나누면 판 수가 나온다.

---

중요한 개념

1. 최대공약수(GCD):
   두 숫자가 공통으로 나누어 떨어지는 가장 큰 숫자.
   
   
2. 최소공배수(LCM):
   두 숫자가 공통으로 나누어 떨어질 수 있는 가장 작은 숫자.

---

[ 코드 단계별 설명 ]

1. 최대공약수(GCD) 구하기

def gcd(a, b):
    while b:  # b가 0이 될 때까지 반복
        a, b = b, a % b  # a와 b를 계속 나눠서 나머지를 구함
    return a  # 마지막에 남는 a가 최대공약수

 

작동 원리:
예를 들어, a=12, b=8이라면:

1. 나머지 계산: 12 % 8 = 4, 그래서 a=8, b=4
2. 다시 계산: 8 % 4 = 0, 그래서 a=4, b=0
3. 최대공약수는 4

 

2. 최소공배수(LCM) 구하기

def lcm(a, b):
    return a * b // gcd(a, b)  # 두 숫자를 곱하고 최대공약수로 나눔

 

작동 원리:
최소공배수는 a * b를 최대공약수로 나누면 된다.
예: a=6, b=4라면:

• gcd(6, 4) = 2
• lcm(6, 4) = (6 * 4) // 2 = 12

 

3. 문제 해결 함수

def solution(n): 
	return lcm(6, n) // 6

• 작동 원리:
  1. lcm(6, n)으로 필요한 피자 조각 수를 구함.
  2. 그 조각 수를 6으로 나눠서 피자 판 수를 계산.