[백준 1188] 음식 평론가

1188번: 음식 평론가

알고리즘 : 수학

난이도 : 골드Ⅳ

 

1. 문제요약

• 요리사가 소시지 n개를 준비하면 이를 m명의 음식평론가가 나눠 먹는다.
• m명의 평론가가 같은 양만큼 소시지를 받을 수 있도록 소시지를 잘라야 한다.
• 100이하의 자연수 n,m이 입력으로 주어지면 소시지를 자르는 최소횟수를 출력한다.

2. 아이디어

• 일단 n과 m이 서로소이면 m-1번 소시지를 잘라야 함은 자명하다.
• n과 m이 서로소가 아닌 경우에는 어떻게 될까? 예를들어 소시지 4개를 평론가 6명이 나누어 먹는 경우를 생각해보면 소시지 2개를 평론가 3명이 나누어 먹는 경우가 두번 반복되는 것임을 알 수 있고, 답은 (3-1)의 두배인 4가 된다.
• 즉, n과 m의 최대공약수를 구하고, m을 최대공약수 t로 나눈 m'에 대하여 (m'-1) * t가 구하는 답이된다.
• 두 정수의 최대공약수를 구하는 방법은 유클리드 호제법 gcd(a,b) = gcd(b,a%b)를 응용하면 쉽게 구할 수 있다.

3. 구현과정

• 두 정수의 최대공약수를 구하는 함수 gcd(x,y)를 정의한다. z = x%y라 할때, z가 1이면 y가 최대공약수가 되므로 y를 return하고, z가 1이 아니면 유클리드 호제법에 따라 gcd(y,z)를 return하면 된다.
• n과 m을 입력받는다.
• m을 최대공약수로 나눈 몫에 1을 빼고, 이 값에 최대공약수를 곱해주면 원하는 답이 된다.

4. 파이썬 코드

def gcd(x, y):
    z = x % y
    if z == 0:
        return y
    else:
        return gcd(y, z)

n, m = map(int, input().split())
t = gcd(n,m)
print((m // t - 1) * t)