[백준/1188/파이썬] 음식 평론가

https://www.acmicpc.net/problem/1188

1188번: 음식 평론가

Problem

• 선영이의 직업은 소시지 요리사이다. 소시지를 팔기 전에 음식 평론가 M명을 모아서 맛을 테스트해보려고 한다.
• 선영이는 동일한 소시지를 총 N개를 준비했다. 이 소시지를 모든 평론가들이 같은 양을 받게 소시지를 자르려고 한다. 이때, 소시지를 자르는 횟수를 최소로 하려고 한다.
• 소시지의 수와 평론가의 수가 주어졌을 때, 모든 평론가에게 같은 양의 소시지를 주기 위해 필요한 칼질의 수를 구하는 프로그램을 작성하시오. 

조건

• 첫째 줄에 소시지의 수 N과 평론가의 수 M이 주어진다. (1 ≤ N, M ≤ 100)

SOL

이번 문제는 수학적인 개념이 좀 필요한 문제였다. 처음에는 이해가 안갔지만, 하나하나 차근차근 따라가면서 이해가 됬던 문제! 

완전탐색

 

소시지가 사람 수 보다 많은경우(N>M)

칼질의 횟수를 F(N,M)이라고 정의하겠다. 그렇다면, N>M인 경우를 생각해보자.

소시지가 10개 있고, 사람이 6명밖에 없다면, 6명에게 1개씩 일단 주고, 나머지 4개를 6명에게 나눠주는 것과 똑같다.

이 부분은 직관적으로 이해하기 쉬울것이다. 그리고 ,칼질의 횟수를 생각해보면, 그냥 1개를 주는건 칼질을 할 필요가 없기 때문에, 아래의 식이 성립하게 된다. 

F(N,M) = F(N%M,M)

 

소시지가 사람 수 보다 적은 경우(N<M)

소시지가 충분하지 않다면, 이제 잘라야 한다. 하지만, 모두에게 공평하게 잘라줘야하기 때문에, N/M조각만큼 나눠야한다. 이걸 이해하기 편하게 하기 위해서, 소시지의 길이가 M이라고 생각을 해보자. 

즉, 소시지가 4개, 사람이 6명인데, 각각의 소시지의 길이가  6m라고 생각하자. (길이는 자유니까)

 

그렇다면, 일단, 4명에게 4m를 나눠줍니다.  그리고, 나머지 2미터 만큼을 , 남은 사람이 나눠가지면 됩니다. 이렇게 되면, M명 중, N명은 우선 받을 필요가 없습니다. 이미, 받을 만큼 받았기 때문입니다.

(이부분이 확 와닿지는 않을겁니다. 천천히 따라와보세요!) 

그렇다면, M-N명이 , 이제 나머지를 나눠갖게되는 문제가 되버립니다. 이때, 칼질은 N번 발생하게 됩니다.

M-N이 0이될때까지, 반복하여 주면 됩니다.

즉, F(N,M) = F(N,M-N) + N

 

최대공약수의 이용

하지만, 이 풀이를 대부분 찾아보면 최대공약수를 이용하게 되는데요, 어떻게 최대공약수를 이용하게 되는지 증명해봅시다. 소시지가 N개, 사람이 M명이면, 한 사람당 소시지는 N/M개 씩 가져가게 됩니다.이때, t명이 소시지를 가져갔다고하면, 소시지는 N/M*t개가 사라지게 됩니다. 이때, N/M*t가 자연수가 되는 구간에서는, 우리는 자를 필요가 없어집니다.

우리는 최소의 cutting 횟수로, 남은 자투리까지 알뜰하게 살려서, m명에게 주게 될겁니다.

예를들어, N=9,M=15 라면, t=5라고 해봅시다. 현재 3/5 조각씩 1명부터 가져간다고 합시다.

1번째 사람은, 1개의 소시지에서, 9/15 만큼 가져가고, 나머지 6/15는 남게 됩니다.

2번째 사람은 , 앞에서 남은 6/15랑 , 1개의 소시지에서 3/15만큼 잘라서 가져갑니다.(자투리를 남기지 않습니다)

3번째 사람은,  소시지가 충분히 남아있기 때문에, 9/15만큼 잘라서 가져갑니다.

4번째 사람은,  앞에서 남은 3/15와 6/15 만큼 잘라서 가져갑니다.

5번쨰 사람은, 운좋게도 남은 소시지의 크기가 딱 가져갈 만큼의 크기가 됩니다. 

우리는 이러한 구간을 찾고 있는겁니다.

• GCD(N,M) = k 라고하고, 합시다. (t*N/M) = t*(N/k) / (M/k) 라고 식을 조작해줍니다. 이때 , n*k,M*k가 자연수가 됩니다.
• 그렇다면, t*Q/Q` 이 되고, Q와 Q`은 서로소 관계가 됩니다. ( 최대 공약수로 나누는 의미는 서로소가 될때 까지 나눈 다는 의미입니다)

즉, t가 Q`의 배수가 될때, t*N/M은 자연수가 됩니다.

예를들어, N=9,M=15라고 하면, gcd(9,15)= 3 , Q는 3, Q`은 5가 나오게됩니다.

t는 1~15까지 자연수인데, 이 중 t가 5의 배수는 5, 10 , 15 이므로,  3가지를 제외해주게 됩니다.

이 식은, M-gcd와 동치관계가 됩니다. 

 

즉, 최대공약수를 이용해서, 풀 수 있게 되는 문제가 됩니다. 

이 문제는 직관적으로, N개의 소시지를 커다란 1개로 생각을해서, 남는걸 상대방에게 우선적으로 쥐어주고, 추가적으로 소시지를 넣어주면 떠올리기 쉬운 문제가 되고, 아니라면 이리저리 헤매게됩니다. 새로운 1개를 꺼내서 새로 잘라주는게 아닙니다!(생각해보면, 현실세계에서도 이렇게 합니다)

 

# 

def GCD(a,b):
    if b==0:
        return a
    return GCD(b,a%b)

N,M=map(int,input().split())
print(M-GCD(max(N,M),min(N,M)))