[1188] 음식 평론가

문제 링크 : https://www.acmicpc.net/problem/1188

1188 - 음식 평론가

본문

선영이의 직업은 소시지 요리사이다. 소시지를 팔기 전에 음식 평론가 M명을 모아서 맛을 테스트해보려고 한다.

선영이는 동일한 소시지를 총 $N$개를 준비했다. 이 소시지를 모든 평론가들이 같은 양을 받게 소시지를 자르려고 한다. 이때, 소시지를 자르는 횟수를 최소로 하려고 한다.

예를 들어, 소시지가 2개, 평론가가 6명있는 경우를 생각해보자. 이때, 각 소시지를 세 조각으로 만든 다음, 각 평론가에게 한 조각씩 주면 된다. 이 경우에 소시지는 총 네 번 자르게 된다. 다른 경우로 소시지가 3개, 평론가가 4명 있는 경우를 생각해보자. 이때는 각 소시지의 크기를 3:1로 잘라서 큰 조각을 평론가에게 하나씩 주고, 남은 조각을 평론가에게 주면 모두 동일한 양을 받게 된다.

소시지의 수와 평론가의 수가 주어졌을 때, 모든 평론가에게 같은 양의 소시지를 주기 위해 필요한 칼질의 수를 구하는 프로그램을 작성하시오.

입력

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

출력

첫째 줄에 모든 평론가에게 동일한 양을 주기 위해 필요한 칼질 횟수의 최솟값을 출력한다.

제한

시간 제한	메모리 제한
1sec	128MB

---

풀이

소시지를 사람들에게 똑같은 크기로 나눠줘야하는 문제이다. 소시지는 한 번에 여러 개를 자르는 것은 불가능하다고 한다.

예시를 조금 들어보자. 소시지의 개수가 3개, 사람이 4명 있다면 각 사람에게 3/4개의 소시지를 주어야 한다. 이 경우는 각 크기만큼 소시지를 잘라주면 된다. 또, 소시지의 개수가 9개, 사람이 4명 있다면 각 사람에게 소시지 2개와 1/4개씩 주어야 한다.

소시지 3개를 4명에게 나눠주기 위해서는 3/4 크기의 조각을 4개 만들어야한다. 그러려면 3개의 소시지를 3/4 크기로 자르고, 남은 3개의 1/4 조각을 1명에게 주면 된다. 자르는 횟수는 3번.

소시지 9개를 4명에게 나눠주기 위해서는 소시지 2개와 1/4 크기의 조각을 4개씩 만들어야한다. 2개의 소시지는 자르지 않고 주어도 되므로, 잘라야 하는 소시지는 1개고, 그 크기는 각각 1/4 크기여야한다. 자르는 횟수는 4번.

규칙을 한 번 찾아보자. 우선 소시지 개수가 사람보다 많거나 같을 경우, 각 사람들에게 1개씩 나누어주어도 된다. 즉 소시지가 $a$개, 사람이 $b$명 있을 때, $a\ge b$라면 $(a,b)$ 상황의 문제는 $(a-b,b)$ 상황의 문제로 바꿔 생각할 수 있다. 이 과정은 계속 반복될 수 있으므로, 결과적으로는 $a<b$인 상황까지 만들어낼 수 있게 된다. 즉, 모든 문제는 $(a,b)\to (a\mathrm{\%}b,b)$ 문제로 바꿔서 풀면 된다.

그러면 그 때의 답은 어떻게 구할 수 있을까? 사람의 수가 $b$이므로, 소시지 조각은 최소 $b$개 만들어야하며, 그 때 필요한 칼질은 $b-1$번 필요할 것 같다. 그런데, 소시지가 2개 있고 사람이 6명 있다면, 각 사람에게 필요한 소시지는 1/3 크기이므로, 2개의 소시지를 1/3 크기로 잘라 총 4번의 칼질만으로도 소시지를 나눠줄 수 있다. 무조건 $b-1$로 계산할 수 없다는 것. 예외상황을 찾아야 한다.

답은 생각보다 간단하다. $a$와 $b$가 서로소인 경우 항상 $b-1$번의 칼질로 소시지를 나눠줄 수 있다. $a/b$ 크기의 소시지로 잘라주면 되기 때문. 그런데 $a$와 $b$의 공약수가 1보다 크다면 굳이 $a/b$ 크기로 자를 필요가 없다. 그의 기약분수 형태로, 조금 더 크게 잘라도 되기 때문. 즉, 최대공약수가 1이 아니라면, $(a,b)$ 문제는 $(a/r,b/r)\times r$ 문제로 바꿀 수 있다는 얘기. 그래서 최대공약수를 찾는 것이 문제의 핵심이다.

$(a,b)$가 서로소인 경우 답은 $b-1$이므로, $a$와 $b$의 최대공약수를 구한 후 문제를 최대공약수로 나눠버린 다음 답을 계산하면 된다. 답은 $(b/r-1)\times r$번.

• 참고 알고리즘 :

코드

사용 언어 : C

최종 수정일 : 2023 / 6 / 15

#include <stdio.h>

int n, m;

int gcd(int a, int b) {
    while (b > 0) {
        int x = a;
        a = b, b = x % b;
    }
    return a;
}

int main() {
    scanf("%d %d", &n, &m);

    n %= m;
    int result;
    
    if (n == 0) {
        result = 0;
    } else {
        result = (m / gcd(m, n) - 1) * gcd(m, n);
    }

    printf("%d", result);
    return 0;
}