백준 1188: 음식 평론가

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

1188번: 음식 평론가

 

풀이

예를 들어서 생각해봅시다. 소시지가 18개, 평론가가 8명 있다고 합시다. 그렇다면 몇 번의 칼질이 최소가 될까요? 

18개의 소시지 중 16개의 소시지는 한 명당 두 개씩 나누어줍니다. 그러면 구하는 것은 소시지가 2개, 평론가가 8명일 때 필요한 칼질의 수가 됩니다. 2개의 소시지를 8개의 조각으로 나누는 것이 가장 효율적이기 때문에 하나의 소시지 당 3번의 칼질을 하면 6번의 칼질로 8명에게 같은 양을 줄 수 있습니다.

소시지가 10개, 평론가가 6명이 있다고 합시다. 10개 중의 6개는 한 명 당 하나씩 나누어주면 됩니다. 그러면 구하는 것은 소시지가 4개, 평론가가 6명일 때 필요한 칼질의 수가 됩니다. 하나의 소시지가 길이가 6이라면 한 명당 4의 길이를 나누어 주면 되기 때문에 4개의 소시지에 대해 각각 길이 4, 2로 나눕니다(4번의 칼질을 사용합니다). 길이 4의 조각을 4명에게 주면 길이 2짜리 4개와 2명의 평론가만 남습니다. 따라서 길이 2짜리의 소시지 2개씩을 주면 해결이 되므로 총 4번의 칼질로 해결할 수 있습니다.

 

위의 예시들을 보면 칼질의 수를 재귀적으로 구할 수 있을 것 같은 느낌이 듭니다. 소시지의 수 N이 평론가의 수 M 이상이라면, 어차피 N개 중 $k\times M\ (k=N/M)$개는 칼질을 안 해도 한 명당 k개씩 줄 수 있으므로 칼질의 수를 F(N, M)이라 하면, $F(N,\ M)=F(N\%M,\ M)$이 됩니다.

 

M이 N보다 크다고 합시다. 그리고 N개의 소시지의 길이가 각각 M이라고 하면, 각 사람은 무조건 길이 N만큼을 받아야 합니다. 따라서 N개의 소시지에 각각 칼질을 하여 길이 N짜리 소시지와 M-N짜리 소시지를 만들 수 있습니다. 그렇게 되면 M명의 평론가 중 N명은 각자 필요한 소시지의 양이 충족되었므로 M-N명만 필요한 양을 가지면 됩니다. 즉, N개의 소시지와 M-N명의 평론가가 있을 때의 칼질 수를 구하는 문제로 변형시킬 수 있습니다. 따라서 앞서 한 N번의 칼질을 생각하면 $F(N,\ M)=F(N,\ M-N)+N$이 됩니다. 이를 계속 반복하다 보면 $F(N,\ M)=F(N,\ M\% N )+N\times (M/N)$으로 구할 수 있겠죠.

 

위의 함수를 보면, 최대공약수가 생각나는 점화식이라는 것을 알 수 있습니다. $F(N,\ M)=M-gcd(N,\ M)$이면 위의 모든 점화식을 만족합니다. 따라서 저희는 최대공약수를 구하여 M에서 최대공약수를 빼서 출력하면 답이 됩니다.

 

코드

위의 풀이로 짠 코드입니다.

#include <bits/stdc++.h>
using namespace std;
int gcd(int n, int m) {
    if(!(n%m)) return m;
    return gcd(m, n%m);
}
int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    if(n>m) cout << m-gcd(n, m);
    else cout << m-gcd(m, n);
}

 

감사합니다.