음식 평론가
백준 1188
GOLD IV
문제 내용
문제 링크
해결 방안
이번 문제는 n개의 소세지를 동일한 비율로 m명에게 나누기 위해 소세지를 자르는 최소 횟수를 구하는 문제이다.
기초부터 풀어나가면, n < m을 만족하는 서로소인 n, m에 대해 n/m만큼 쪼개기 위해서는 반드시 최소 m-1번의 칼질을 해야 한다. 이는 소세지 여러 개를 하나의 소세지라고 생각하면 반드시 m-1번의 칼질이 필요하다는 것을 알 수 있다.
원래는 하나의 소세지가 아니기 때문에, 칼질을 하려는 부분이 각 소세지의 끝과 끝이 맞닿아 있는 부분이라면 칼질을 하지 않아도 된다. n개의 소세지를 자르는 중 소세지 끝이 이미 나뉘어 칼질을 하지 않기 위해서는 n과 m에 1이 아닌 공약수가 있어야 하며, 공약수가 있다는 것은 현재 소세지를 공약수만큼 소분화할 수 있다는 것이다. 이때, n과 m의 공약수만큼 소분화했을 때 나눈 각 동일한 집합들은 서로소일 때 하나의 소세지처럼 간주할 수 있으므로, n과 m을 가장 작은 자연수의 비로 나타냈을 때의 결과를 n과 m의 공약수만큼 반복하면 된다. 이렇게 소세지를 잘랐을 때 소세지 하나의 크기는 n/m으로, 공약수에 관계 없이 항상 일정하기 때문에 하나의 소세지를 자르는 횟수를 반복하는 것과 같다.
결론적으로, n과 m이 서로소일 때와 서로소가 아닐 때를 각각 구분지어 문제를 해결하면 된다. n과 m이 서로소일 경우, 하나의 소세지를 자르는 것처럼 간주하며 m-1번의 칼질이 최소 횟수가 된다. 반대로 n과 m이 서로소가 아닌 경우, 서로소일 떄의 소세지 개수가 공약수만큼 늘어난 것과 같으므로 가장 작은 자연수의 비일때의 자르는 횟수를 최대공약수만큼 반복해주면 된다.
서로소(coprime)란?
두 정수 a, b에 대해 최대공약수가 1이라면, 두 정수 a와 b는 서로소(coprime)라고 말한다. 서로소인 두 정수는 그 자체로 가장 작은 정수의 비로 나타나 있으며, 최대공배수가 서로의 곱이다. 두 정수가 소수(prime)인가와 서로소인가는 서로 독립사건이며, 두 정수가 모두 짝수이면 반드시 서로소가 아니다.
풀이 코드
#include <iostream>
using namespace std;
// 유클리드 호제법(최대공약수 반환)
int gcd(int a, int b) {
if(b == 0) return a;
return gcd(b, a % b);
}
int main() {
int n, m;
cin >> n >> m;
// n과 m의 최대공약수 계산
int div = gcd(n % m, m);
// n과 m의 가장 작은 자연수의 비
m /= div;
// m-1에 최대공약수 곱셈
cout << div * (m - 1) << endl;
return 0;
}